++ to everyone who contributed to this thread,
choroba,
johngg,
atcroft among others for their examples and efforts to explain.
As already said I found the
choroba's code faster than the
johngg's marvellous one, given the first one was optimized with a premature return in the foreach loop adding
if($i%2==0){next}.
It seems reasonably; there are a lot of numbers (in fact an half of the whole..) that divides by 2. Also a lot that divides by 3. In fact adding this premature return check for number 3 was even faster.
So my (erroneous) thought was: maybe a check against all yet obtained primes can be the best optimization. I added a succint
map { next if $i % $_ == 0 } @primes; at the top of the for loop and it revealed to be slow like a dead snail:
Rate primes_all ch jg ch_opt2
primes_all 1.75/s -- -96% -97% -97%
ch 49.8/s 2751% -- -4% -11%
jg 51.9/s 2869% 4% -- -8%
ch_opt2 56.2/s 3117% 13% 8% --
So the fastest code need to check for a few primes not all. But how many? Adding a check for 5, 7 .. seemed to made the code faster. But i'm to lazy to cut and paste a lot of code so i wrote a code generator to have all optimized subs for primes from 2 to 149.
UPDATE:The section below is based on a wrong assumption! as spotted by
choroba
#! /usr/bin/perl
use warnings;
use strict;
####
print '
use strict;
use warnings;
use Benchmark qw{ cmpthese };
sub primes_original {
my $n = shift;
return if $n < 2;
my @primes = (2);
for my $i (3 .. $n) {
my $sqrt = sqrt $i;
my $notprime;
for my $p (@primes) {
last if $p > $sqrt;
$notprime = 1, last if 0 == $i % $p;
}
push @primes, $i unless $notprime;
}
return @primes
}
';
my @givenp = qw(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 7
+1 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149);
foreach my $num (0..$#givenp){
####
print '
sub primes_opt_till_'.$givenp[$num].' {
my $n = shift;
return if $n < 2;
my @primes = (2);
for my $i (3 .. $n) {
';
foreach my $quot ( 0 .. $num ){
####
print "\t\t\t\t".'if($i%'.$givenp[$quot].'==0){next}'."\n";
}
####
print '
my $sqrt = sqrt $i;
my $notprime;
for my $p (@primes) {
last if $p > $sqrt;
$notprime = 1, last if 0 == $i % $p;
}
push @primes, $i unless $notprime;
}
return @primes
}
##
';
}
####
print '
cmpthese(-10,
{
primes_original => \'primes_original (10000)\',
';
foreach my $num (0..$#givenp){
print "opt_till_$givenp[$num] => 'primes_opt_till_$givenp[$num] (1
+0000)',\n";
}
####
print'
});
';
And i had a simpatic 1446 lines program ready to overheat my CPUs. I run it few times and results vary but the winner seems to be a prime number between 61 and 89.
In fact preformance increse constantly for primes between 2 and 53 and decrease constantly for primes from 101 to 149.
So choosen 79 as the winner, the fastest code to check primality for numbers from 1 to 10000 can be as ugly as:
sub primes_opt_till_79 {
my $n = shift;
return if $n < 2;
my @primes = (2);
for my $i (3 .. $n) {
if($i%2==0){next}
if($i%3==0){next}
if($i%5==0){next}
if($i%7==0){next}
if($i%11==0){next}
if($i%13==0){next}
if($i%17==0){next}
if($i%19==0){next}
if($i%23==0){next}
if($i%29==0){next}
if($i%31==0){next}
if($i%37==0){next}
if($i%41==0){next}
if($i%43==0){next}
if($i%47==0){next}
if($i%53==0){next}
if($i%59==0){next}
if($i%61==0){next}
if($i%67==0){next}
if($i%71==0){next}
if($i%73==0){next}
if($i%79==0){next}
my $sqrt = sqrt $i;
my $notprime;
for my $p (@primes) {
last if $p > $sqrt;
$notprime = 1, last if 0 == $i % $p;
}
push @primes, $i unless $notprime;
}
return @primes
}
And for completeness an example of benchmark results (cutted to fit here)
Rate
primes_original 74.2/s
opt_till_2 91.8/s
opt_till_3 108/s
opt_till_5 119/s
opt_till_7 128/s
opt_till_11 134/s
opt_till_13 140/s
opt_till_17 142/s
opt_till_19 151/s
opt_till_23 156/s
opt_till_29 158/s
opt_till_31 164/s
opt_till_37 165/s
opt_till_149 169/s
opt_till_139 169/s
opt_till_41 172/s
opt_till_131 174/s
opt_till_137 174/s
opt_till_127 175/s
opt_till_47 176/s
opt_till_113 178/s
opt_till_43 180/s
opt_till_109 181/s
opt_till_53 181/s
opt_till_107 184/s
opt_till_59 184/s
opt_till_103 186/s
opt_till_101 188/s
opt_till_61 188/s
opt_till_97 189/s
opt_till_67 190/s
opt_till_71 190/s
opt_till_73 191/s
opt_till_89 191/s
opt_till_83 192/s
opt_till_79 193/s
L*
There are no rules, there are no thumbs..
Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.
