How can I make my prime number generator better?

[nikolas.britton]

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]

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);"

 

[nikolas.britton]

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
Thanks for your help.

 

[Octo]

On 23 Mar, 08:53, (e-mail address removed) wrote:

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:

 

[Marc Espie]

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.

 

[anno4000]

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]

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...

 

[anno4000]

(e-mail address removed) ([email protected]) wrote on MMMMCMLII
September MCMXCIII in
<URL@ 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