|
Re^8: Number functions.. primes (ugly code runs faster)
by Discipulus (Canon) on Apr 07, 2015 at 09:06 UTC
|
why aren't you eliminating the numbers which end with 2, 4, 5, 6, 8, and 0 before doing any math
If you want you can, but how do you spot those numbers? you are using a regex that, as you can guess, is slower than math checks. Theese numbers will be catched with the modulo operator anyway, as choroba explained.
Also the regex in the original code is also not correct: you skip 2 and 5.
perl -e "map {print qq($_ ) unless $_ =~/(2|4|5|6|8|0)$/ } @ARGV" 2 3
+5 7 11 13 17 19 23 29 37
3 7 11 13 17 19 23 29 37
i used a different regex (and precompiled in the bench program using qr'\d[245680]$'):
perl -e "map {print qq($_ ) unless $_ =~/\d[245680]$/ } @ARGV" 2 3 5 7
+ 11 13 17 19 23 29 37
2 3 5 7 11 13 17 19 23 29 37
About saving time skipping numbers ending with some fixed digit, as said, the regex solution is slower: with this code:
You will see a significant decreese of speed if you skip numbers using a regex:
1..1
ok 1 - same
Rate primes_skipper primes_original primes_o
+pt_till_11
primes_skipper 33.5/s -- -35%
+ -94%
primes_original 51.4/s 53% --
+ -90%
primes_opt_till_11 519/s 1448% 909%
+ --
HtH
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] |
|
|
Here are some of the problems.
- Some made assumptions I knew the regex was slowing down my code. I had no idea the regex was the problem.
- Some made assumptions of my prowess in math. If it isn't addition, subtraction, multiplication, or division; I won't think to use it. So, using sqrt is confusing.
- Only aaron_baugher commented directly on my code and showed me where I overdid it with the check for divisibility by 9. Everyone else wrote their own versions without commenting on the code I provided first.
- No one commented their code! I'm still stuck back at choroba's first prime example at the square root test. Adding the use of square roots still bothers me for some reason.
Like with many car shows my hubby watches where the show glosses over a lot, it is like you took the logo off the car, trashed the car, and put the logo on another car. I still don't know what is so wrong with the original car (function) that the only thing worth saving was the logo (function name). So take one part out at a time, explain why it is broken, then install the new part telling the audience why the new part is better. Pretty please?
No matter how hysterical I get, my problems are not time sensitive. So, relax, have a cookie, and a very nice day!
Lady Aleena
| [reply]
[d/l] |
|
|
I also struggle with Math!!
A number cannot be prime if it is a perfect square.
16 is perfect square of 4. 16 not prime.
A number is only prime if two other integers cannot be multiplied together to equal that number.
Take 37, sqrt = 6.08
- So as you iterate over the numbers..
- 37 % 2 == 0, nope. Another way to say is that 2 * something = 37 with no remainder
- 37 % 3 == 0, nope. Another way to say is that 3 * something = 37 with no remainder
- 37 % 4 == 0, nope. Another way to say is that 4 * something = 37 with no remainder
- 37 % 5 == 0, nope. Another way to say is that 5 * something = 37 with no remainder
- 37 % 6 == 0, nope. Another way to say is that 6 * something = 37 with no remainder
Our next number would be 7. But we know that
6.08 times any number smaller than 6.08 is < 37
and 6.08 times any number larger than 6.08 is > 37
So, in our next iteration, 7 * something = 37 with no remainder, for that something to multiply 7 and make 37, would *have* to be smaller than 6.08, and we already tested all those.
Does that sound right?
| [reply] |
|
|
| [reply] |
Re^8: Number functions.. primes (ugly code runs faster)
by Anonymous Monk on Apr 07, 2015 at 05:29 UTC
|
| [reply] |
|
|
| [reply] |
|
|
Hello Lady_Aleena,
You are correct, and by eliminating even numbers up front, along with multiples of five, choroba’s solution can be speeded up by around a third:
But note that choroba’s solution is well over a hundred times faster than the non-sieve method you posted, so maybe an additional speedup of around 35% was irrelevant to the point he was making. :-)
Hope that helps,
| [reply]
[d/l]
[select] |
|
|
I think the reason is in your own words :-)
doing math on numbers
The Perl compiler probably knows that $number % 2 is just "testing the last bit", which probably is more efficient than even the most optimized regex for testing "even"-ness. Plus you don't need to add 2 back in.
I assume, because $number is populated by counting, Perl doesn't even need to convert from string to number, so the other special cases are possibly also not an optimization.
For a human Perl Interpreter, of course, the situation looks different :-)
| [reply]
[d/l]
[select] |