Home > Archive > PERL Beginners > March 2007 > Primality testing... need more speed.
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Primality testing... need more speed.
|
|
| Nikolas Britton 2007-03-22, 9:58 pm |
| Any ideas for making the code below faster? Can I get more speed if I
changed the algorithm, if so... how? What's the fastest way to test
extremely large primes like 2^1398269-1? Why is Big:Int so slow? How
can I get rid of the goto breaks in my code? Thanks...
#!/usr/bin/perl
use strict;
use sigtrap;
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 point 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 point 2.
print "$y1\n";
} end2:
$k++;
}
| |
|
| Hi,
What about using a CPAN module like
http://search.cpan.org/~schubiger/M...ath/Prime/XS.pm
?
--
tfe
http://tfeserver.homelinux.com
On 22 mar, 13:03, "Nikolas Britton" <nikolas.brit...@gmail.com> wrote:
> Any ideas for making the code below faster? Can I get more speed if I
> changed the algorithm, if so... how? What's the fastest way to test
> extremely large primes like 2^1398269-1? Why is Big:Int so slow? How
> can I get rid of the goto breaks in my code? Thanks...
>
> #!/usr/bin/perl
> use strict;
> use sigtrap;
> 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 point 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 point 2.
> print "$y1\n";
> } end2:
>
> $k++;
>
> }
| |
| Nikolas Britton 2007-03-22, 9:58 pm |
| On Mar 22, 10:40 am, "tfe" <tfeser...@gmail.com> wrote:
> Hi,
>
> What about using a CPAN module likehttp://search.cpan.org/~schubiger/Math-Prime-XS-0.17/lib/Math/Prime/X...
> ?
I could use Math::Prime::XS but my script is academic, using pre-built
modules would defeat the purpose of trying to learn more about Perl
and proper programming. Thanks for the suggestion though.
[color=darkred]
>
> On 22 mar, 13:03, "Nikolas Britton" <nikolas.brit...@gmail.com> wrote:
>
>
>
>
>
>
>
>
|
|
|
|
|