20 ms·
I'm not exactly sure I understand the algorithm, but if it is only supposed to generate prime numbers upto 1000, than it appears to erroneously include `999` as
by lizmat 9y ago
I'm not exactly sure I understand the algorithm, but if it is only supposed to generate prime numbers upto 1000, than it appears to erroneously include `999` as a prime number.
FWIW, if I would just be interested in the prime numbers upto 1000, I would write that like this:
(1..1000).grep( *.is-prime )
Which for me executes within noise of your Perl 5 algorithm. For larger values on multi-CPU machines, I would write this as:
(1..2500).hyper.grep( *.is-prime )
Around 2500 it becomes faster to `hyper` it, so the work gets automatically distributed over multiple CPU's.
Am currently researching as to why your Perl 6 algorithm is so slow.
- petre 9y agoThe algorithm is an implementation of the Sieve of Sundaram. 999 might have slipped in by an off by one error. Thanx for the suggestion of using is-prime, but in order to benchmark multiple languages, I need to run the same thing everywhere.
- lizmat 9y agoTurns out that even though primes are integers, in your Perl 6 version, every calculation was done by using floating point. And this was caused by the call to the subroutine. If you would do: sieve_sundaram(1000) instead of: sieve_sundaram(1e3) then it all of a sudden becomes 4x as fast. In Perl 5 you never know what you're dealing with with regards to values. In Perl 6 if you tell it to use a floating point, it will infect all calculations to be in floating point afterwards. `1e3` is a floating point value. `1000` is an integer in Perl 6. Also, you seem to have a sub-optimal algorithm: the second `foreach` doesn't need to go from `1..$n`, but can go from `$i..$n` instead. This brings down the runtime of the Perl 5 version of the code to 89 msecs for me. Since your program is not using BigInt in the Perl 5 version, it is basically using native integers. In Perl 6, all integer calculations are always BigInts, unless you mark them as native. If I adjust your Perl 6 version for this, the runtime goes down from 4671 msecs to 414 msecs for this version: sub sieve_sundaram(int $n) { my %a; my int @s = 2; my int $m = $n div 2 - 1; for 1..$n -> int $i { for $i..$n -> int $j { my int $p = $i + $j + 2 * $i * $j; if $p < $m { %a{$p} = True; } } } for 1..$m -> int $k { if ! %a{$k} { my int $q = 2 * $k + 1; @s.push($q); } } return @s; } sieve_sundaram(1000); So, about 11x faster than before. And just under 5x as slow as the Perl 5 version. I could further make this idiomatic Perl 6, but the most idiomatic version I've already mentioned: `(1..1000).grep( *.is-prime)`
- petre 9y agoCan we please continue this discussion out of this thread, on a proper Perl forum? I haven't found any contact pointers for you or Ultimatt.
- lizmat 9y agohttps://stackoverflow.com/questions/tagged/perl6 https://stackoverflow.com/questions/tagged/perl6 perhaps? Or on IRC: #perl6 on irc.freenode.org ? Or the perl6-users mailing list?
- petre 9y agoAllright. https://stackoverflow.com/questions/49607801/perl6-vs-perl5-benchmarking-using-prime-numbers https://stackoverflow.com/questions/49607801/perl6-vs-perl5-...