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.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% --
#! /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 for completeness an example of benchmark results (cutted to fit here)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 }
L*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
In reply to Re^4: Number functions.. primes (ugly code runs faster)
by Discipulus
in thread Number functions I have lying around
by Lady_Aleena
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |