Velocity Reviews > Perl > How can I make my prime number generator better?

How can I make my prime number generator better?

nikolas.britton@gmail.com
Guest
Posts: n/a

 03-23-2007
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++;
}

Klaus
Guest
Posts: n/a

 03-23-2007
On Mar 23, 1:47 am, (E-Mail Removed) 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

nikolas.britton@gmail.com
Guest
Posts: n/a

 03-23-2007
On Mar 22, 8:24 pm, "Klaus" <(E-Mail Removed)> wrote:
> On Mar 23, 1:47 am, (E-Mail Removed) 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

Octo
Guest
Posts: n/a

 03-23-2007
On 23 Mar, 08:53, (E-Mail Removed) 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

Marc Espie
Guest
Posts: n/a

 03-23-2007
In article <(E-Mail Removed). com>,
<(E-Mail Removed)> 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.

Guest
Posts: n/a

 03-23-2007
Michele Dondi <(E-Mail Removed)> wrote in comp.lang.perl.misc:
> On Fri, 23 Mar 2007 12:39:38 +0000 (UTC), http://www.velocityreviews.com/forums/(E-Mail Removed) (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

Marc Espie
Guest
Posts: n/a

 03-23-2007
In article <(E-Mail Removed)>,
Michele Dondi <(E-Mail Removed)> wrote:
>On Fri, 23 Mar 2007 12:39:38 +0000 (UTC), (E-Mail Removed) (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...

Guest
Posts: n/a

 03-23-2007
Abigail <(E-Mail Removed)> wrote in comp.lang.perl.misc:
> (E-Mail Removed) ((E-Mail Removed)) wrote on MMMMCMLII
> September MCMXCIII in
> <URL:news:(E-Mail Removed) legroups.com>:
> @@ 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