in reply to Re: Number functions I have lying around in thread Number functions I have lying around
A few questions for you choroba...
- Why aren't you eliminating numbers which end with 2, 4, 5, 6, 8, and 0 right off the bat?
- If sqrt($number) == int(sqrt($number), then you wouldn't have to go through the @primes loop, right?
- What is the @primes loop doing?
- I think $n stands for "number", but what do $i and $p represent??
Thank you for stopping by.
No matter how hysterical I get, my problems are not time sensitive. So, relax, have a cookie, and a very nice day!
Lady Aleena
Re^3: Number functions I have lying around
by choroba (Cardinal) on Mar 31, 2015 at 20:24 UTC
|
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.
| [reply] [d/l] [select] |
|
++ 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] |
|
|
|
|
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] |
|
|
|
|
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] |
|
|