|
in reply to Re^2: Number functions I have lying around
in thread Number functions I have lying around
Here's the algorithm in plain words: Let's create the list of primes up to $n. We start with just 2 as the known prime. Then, for each number $i between 3 and $n, we do the following: we try to divide the number $i by all the known primes up to sqrt $i. If any of them divides the number, then it can't be prime. If none of them divides it, it is a prime, though: because a) if a non-prime $d divides $i, then $d = $p1 * $d1, where $p1 is prime, and $p1 divides $i; b) if a number $p2 greater than sqrt $i divides $i, then $i / $p2 must be less than sqrt $i, and it must divide $i. If we find a new prime, we push it to the list.
- I don't eliminate numbers ending with 2, 4, 5, 6, 8, and 0, because they get eliminated in the 0 == $i % $p test.
- testing every number for sqrt $i == int sqrt $i wouldn't help us much, as it happens rarely.
- the @primes loop, as described above, tries to divide the candidate $i by all the known primes up to sqrt $i, to check its primality.
- $n represents the highest number, we are interested in primes less or equal $n. $i is the candidate, i.e. the number we might include in the @primes list if it passes the primality test. $p is a known prime less or equal sqrt $i.
|
Re^4: Number functions.. primes (ugly code runs faster)
by Discipulus (Canon) on Apr 02, 2015 at 07:00 UTC
|
++ 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
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.
| [reply]
[d/l]
[select] |
|
|
Trying to divide by the known primes is what the algorithm does. Hardcoding some of the values might speed it up, but notice that your solution fails the tests - it doesn't return all the hardcoded primes.
| [reply] |
|
|
Thanks for spotting it. Lesson learned: never skip tests for data with more than five elements.
So for the prime number 149 the hardcoded check has to be:
if($i > 149 && $i % 149 == 0){next}
All the matter about how many primes check to hardcode and about increese and decreese of performances was vain.
But even if it was just a divertissment now i have to go on..
With the correct code, primes between 11 and 37 gives good results, especially 11.
The prime number 11 was the winner benchmarking prime reserch in numbers up to 10K, 100K e 1M.
So the answer is no more 42.
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.
| [reply]
[d/l] |
|
|
|
|
| |
|
| |
|
All of the code for primes() I've seen on this thread are 2-10x slower than any of the four shown on RosettaCode for this task.
If you want the fastest speed, use the ntheory module -- is_prime for primality testing, primes or forprimes or one of the related functions for generating primes. This will be a few orders of magnitude faster.
| [reply] |
|
|
sub sieve_s2 {
my ($n, $i, $s, $d, @primes) = (shift, 7);
my $sieve = '110010101110101110101110111110' .
'101111101110101110101110111110' x ($n/30);
for ($sieve) {
until (($s = $i*$i) > $n) {
$d = 2*$i;
do { substr($_, $s, 1, '1') } until ($s += $d) > $n;
1 while substr($_, $i += 2, 1);
}
$_ = substr($_, 1, $n);
push @primes, pos while m/0/gogo;
return @primes;
}
}
Pure perl isn't up to warp-speed, understandably.
| [reply]
[d/l]
[select] |
|
|
|
|
| |
|
if($i%2==0){next}
(etc.) with
$i%2 or next;
Perhaps naively, I think you would, since you'd eliminate (1) a lexical scope, with all of its setup and teardown; and (2) a numeric comparison.
I reckon we are the only monastery ever to have a dungeon stuffed with 16 ,000 zombies.
| [reply]
[d/l]
[select] |
|
|
