Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

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++;
}

 
Reply With Quote
 
 
 
 
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

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

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



 
Reply With Quote
 
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.
 
Reply With Quote
 
anno4000@radom.zrz.tu-berlin.de
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
 
Reply With Quote
 
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...
 
Reply With Quote
 
anno4000@radom.zrz.tu-berlin.de
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
Re: Infinite prime number generator John Posner Python 0 06-29-2010 06:31 PM
Beginners prime number generator Joel Mayes C Programming 10 12-13-2006 09:17 PM
Random Prime Generator/Modular Arithmetic Tuvas Python 20 03-06-2006 11:47 PM
Prime numbers: addative property modulo p, where p is prime Jeremy Fischer Perl Misc 0 01-16-2005 05:53 PM



Advertisments