# How can I make my prime number generator better?

Discussion in 'Perl Misc' started by nikolas.britton@gmail.com, Mar 23, 2007.

1. ### Guest

How can I improve my code?... faster, better style, proper programming
techniques, better algorithm? Thanks!

#!/usr/bin/perl
use strict;
use warnings;
use diagnostics;

my \$n = 100000; #limit at 6 * 10^14, regex's break.
my \$k = 6; #6 * 10^14, min value is 6.
\$k = int((\$k / 6) + .5);
my \$y1; my \$y2;

for (1 .. int((\$n * .1665) + .5)) {

#check 6k - 1:
\$y1 = ((6 * \$k) - 1);
if (\$y1 !~ m/5\$/o) {
for (1 .. (int((sqrt(\$y1) * .1665) + .5))) {
\$y2 = ((6 * \$_) - 1);
goto end1 if ((\$y1 / \$y2) !~ m/\./o);
\$y2 += 2;
goto end1 if ((\$y1 / \$y2) !~ m/\./o);
}
#is prime tap 1:
print "\$y1\n";
} end1:

#check 6k + 1:
\$y1 += 2;
if (\$y1 !~ m/5\$/o) {
for (1 .. (int((sqrt(\$y1) * .1665) + .5))) {
\$y2 = ((6 * \$_) - 1);
goto end2 if ((\$y1 / \$y2) !~ m/\./o);
\$y2 += 2;
goto end2 if ((\$y1 / \$y2) !~ m/\./o);
}
#is prime tap 2:
print "\$y1\n";
} end2:

\$k++;
}

, Mar 23, 2007

2. ### KlausGuest

On Mar 23, 1:47 am, wrote:
> How can I improve my code?... faster, better style, proper programming
> techniques, better algorithm? Thanks!

As far as the goto's are concerned:

perldoc perlsyn (section "Goto") :
++ In almost all cases like this, it's usually a far, far better idea
++ to use the structured control flow mechanisms of next, last,
++ or redo instead of resorting to a goto. For certain
++ applications, the catch and throw pair of eval{} and die()
++ for exception processing can also be a prudent approach.

I would suggest to wrap an additional { ... } block around the "if
(\$y1 !~ m/5\$/o) { ... }" statement. The additional block will be
labled "end1:", and the "goto" will be replaced by "last".

[ snip ]

> \$y1 = ((6 * \$k) - 1);

end1: { # additional block labeled end1:

> if (\$y1 !~ m/5\$/o) {
> for (1 .. (int((sqrt(\$y1) * .1665) + .5))) {
> \$y2 = ((6 * \$_) - 1);
> goto end1 if ((\$y1 / \$y2) !~ m/\./o);

last end1 if ((\$y1 / \$y2) !~ m/\./o);

> \$y2 += 2;
> goto end1 if ((\$y1 / \$y2) !~ m/\./o);

last end1 if ((\$y1 / \$y2) !~ m/\./o);

> }
> #is prime tap 1:
> print "\$y1\n";

} # remove the old label end1 here
} # close the additional block

There is also a test "if ((\$y1 / \$y2) !~ m/\./o);"

The "/o" regexp-modifier is only useful if there is an interpolated
variable inside the regexp (which is not the case here), so the "/o"
could be removed from the regexp.
But I would suggest to get rid of the regexp alltogether and replace
it by a simple "if (\$y1 % \$y2 == 0);"

--
Klaus

Klaus, Mar 23, 2007

3. ### Guest

On Mar 22, 8:24 pm, "Klaus" <> wrote:
> On Mar 23, 1:47 am, wrote:
>
> > How can I improve my code?... faster, better style, proper programming
> > techniques, better algorithm? Thanks!

>
> As far as the goto's are concerned:
>
> perldoc perlsyn (section "Goto") :
> ++ In almost all cases like this, it's usually a far, far better idea
> ++ to use the structured control flow mechanisms of next, last,
> ++ or redo instead of resorting to a goto. For certain
> ++ applications, the catch and throw pair of eval{} and die()
> ++ for exception processing can also be a prudent approach.
>
> I would suggest to wrap an additional { ... } block around the "if
> (\$y1 !~ m/5\$/o) { ... }" statement. The additional block will be
> labled "end1:", and the "goto" will be replaced by "last".
>
> [ snip ]
>
> > \$y1 = ((6 * \$k) - 1);

>
> end1: { # additional block labeled end1:
>
> > if (\$y1 !~ m/5\$/o) {
> > for (1 .. (int((sqrt(\$y1) * .1665) + .5))) {
> > \$y2 = ((6 * \$_) - 1);
> > goto end1 if ((\$y1 / \$y2) !~ m/\./o);

>
> last end1 if ((\$y1 / \$y2) !~ m/\./o);
>
> > \$y2 += 2;
> > goto end1 if ((\$y1 / \$y2) !~ m/\./o);

>
> last end1 if ((\$y1 / \$y2) !~ m/\./o);
>
> > }
> > #is prime tap 1:
> > print "\$y1\n";

>
> } # remove the old label end1 here
> } # close the additional block
>
> There is also a test "if ((\$y1 / \$y2) !~ m/\./o);"
>
> The "/o" regexp-modifier is only useful if there is an interpolated
> variable inside the regexp (which is not the case here), so the "/o"
> could be removed from the regexp.
> But I would suggest to get rid of the regexp alltogether and replace
> it by a simple "if (\$y1 % \$y2 == 0);"
>

Yes the modulus operation is much faster, benchmark says about 200%
faster! Thanks!!! I would like to get rid of the goto's but I'm not
sure what you wrote will work. I'm using them to break and to jump
over the 'prime plucker' code. I've changed some of the comments and
labels to help convey what it's doing:

#!/usr/bin/perl
use diagnostics;
use warnings;
use strict;

my \$n = 1000; #sets upper bound, max value is 10 ** 15.
my \$k = 6; #sets lower bound, min value is 6.
\$k = int(\$k / 6 + .5);
my \$y1; my \$y2;

for (1 .. int(\$n * .1665 + .5)) {

#do 6k - 1:
\$y1 = (6 * \$k - 1);
if (\$y1 !~ /5\$/) { #separate wheat from chaff:
for (1 .. int(sqrt(\$y1) * .1665 + .5)) {
\$y2 = (6 * \$_ - 1);
goto not_prime_1 if (\$y1 % \$y2 == 0);
\$y2 += 2;
goto not_prime_1 if (\$y1 % \$y2 == 0);
} #prime plucker 1:
print "\$y1 is prime.\n";
} not_prime_1:

#do 6k + 1:
\$y1 += 2;
if (\$y1 !~ /5\$/) { #separate wheat from chaff:
for (1 .. int(sqrt(\$y1) * .1665 + .5)) {
\$y2 = (6 * \$_ - 1);
goto not_prime_2 if (\$y1 % \$y2 == 0);
\$y2 += 2;
goto not_prime_2 if (\$y1 % \$y2 == 0);
} #prime plucker 2:
print "\$y1 is prime.\n";
} not_prime_2:
++\$k;
}

END

, Mar 23, 2007
4. ### OctoGuest

On 23 Mar, 08:53, wrote:
<snip>
> Yes the modulus operation is much faster, benchmark says about 200%
> faster! Thanks!!! I would like to get rid of the goto's but I'm not
> sure what you wrote will work.

<snip>

I've amended your code to illustrate what was suggested:

> #!/usr/bin/perl
> use diagnostics;
> use warnings;
> use strict;
>
> my \$n = 1000; #sets upper bound, max value is 10 ** 15.
> my \$k = 6; #sets lower bound, min value is 6.
> \$k = int(\$k / 6 + .5);
> my \$y1; my \$y2;
>
> for (1 .. int(\$n * .1665 + .5)) {
>
> #do 6k - 1:
> \$y1 = (6 * \$k - 1);

P1: {
> if (\$y1 !~ /5\$/) { #separate wheat from chaff:
> for (1 .. int(sqrt(\$y1) * .1665 + .5)) {
> \$y2 = (6 * \$_ - 1);
> last P1 if (\$y1 % \$y2 == 0);

^^^^^^^
> \$y2 += 2;
> last P1 if (\$y1 % \$y2 == 0);

^^^^^^^
> } #prime plucker 1:
> print "\$y1 is prime.\n";
> }

}
>
> #do 6k + 1:
> \$y1 += 2;

P2: {
> if (\$y1 !~ /5\$/) { #separate wheat from chaff:
> for (1 .. int(sqrt(\$y1) * .1665 + .5)) {
> \$y2 = (6 * \$_ - 1);
> last P2 if (\$y1 % \$y2 == 0);

^^^^^^^
> \$y2 += 2;
> last P2 if (\$y1 % \$y2 == 0);

^^^^^^^
> } #prime plucker 2:
> print "\$y1 is prime.\n";
> }

}
> ++\$k;
>
> }
>
> END

Octo, Mar 23, 2007
5. ### Marc EspieGuest

In article <>,
<> wrote:
>How can I improve my code?... faster, better style, proper programming
>techniques, better algorithm? Thanks!

Get rid of floating point arithmetic. Instead of time-consuming operation,
like looping from 1 to sqrt(n), write a while loop that stops when
i*i >= n.

As far as algorithms go, look up `Erathosthene's sieve', probably on wikipedia.

Marc Espie, Mar 23, 2007
6. ### -berlin.deGuest

Michele Dondi <> wrote in comp.lang.perl.misc:
> On Fri, 23 Mar 2007 12:39:38 +0000 (UTC), (Marc Espie)
> wrote:
>
> >Get rid of floating point arithmetic. Instead of time-consuming operation,
> >like looping from 1 to sqrt(n), write a while loop that stops when
> >i*i >= n.

>
> sqrt(n) can be precalculated, i*i must be calculated for every loop.

Not necessarily. If the algorithm involves the calculation of n/i
to determine divisibility, you can equivalently check for i >= n/i
at no extra cost.

Anno

-berlin.de, Mar 23, 2007
7. ### Marc EspieGuest

In article <>,
Michele Dondi <> wrote:
>On Fri, 23 Mar 2007 12:39:38 +0000 (UTC), (Marc Espie)
>wrote:
>
>>Get rid of floating point arithmetic. Instead of time-consuming operation,
>>like looping from 1 to sqrt(n), write a while loop that stops when
>>i*i >= n.

>
>sqrt(n) can be precalculated, i*i must be calculated for every loop.
>

Perl being interpreted, you can apply known optimizations to it,
namely, (i+1)*(i+1) = i*i + 2*i + 1...

Marc Espie, Mar 23, 2007
8. ### -berlin.deGuest

Abigail <> wrote in comp.lang.perl.misc:
> () wrote on MMMMCMLII
> September MCMXCIII in
> <URL:news:>:
> @@ How can I improve my code?... faster, better style, proper programming
> @@ techniques, better algorithm? Thanks!
>
> A better algorith beats everything else.
>
> If you want to generate prime numbers starting from 1, sieves are your
> best option. They have been your best option since antiquity.
>
> Here's an example of a sieve:
>
>
> #!/opt/perl/bin/perl -l
>
> # A sieve based on base 6. Only possible primes are those numbers p
> # for which p mod 6 == 1, or p mod 6 == 5.
> #
> # Let n = 6 * k + l (0 <= l < 6). Then the bit b associated with n is
> # b = 2 * k + [undef, 0, undef, undef, undef, 1] -> [l]
> # In reverse, given a bit b, the corresponding number n is
> # n = 6 * int (b / 2) + [1, 5] -> [b % 2].

[snip

Ah, I remember that. You developed it from a modest beginning (base 10,
if memory serves) to this form in steps, posting and discussing intermediate
implementations on clpm. That was fun.

Anno

-berlin.de, Mar 23, 2007