Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot

Re^5: Number functions.. primes (ugly code runs faster)

by danaj (Friar)
on May 01, 2015 at 06:31 UTC ( [id://1125331] : note . print w/replies, xml ) Need Help??

in reply to Re^4: Number functions.. primes (ugly code runs faster)
in thread Number functions I have lying around

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.

  • Comment on Re^5: Number functions.. primes (ugly code runs faster)

Replies are listed 'Best First'.
Re^6: Number functions.. primes (ugly code runs faster)
by Anonymous Monk on May 02, 2015 at 17:20 UTC

    Sounds like a challenge. I took the dj_string routine on rosettacode and simplified it some.

    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.

      Very nice. About 1.5x faster, better looking code, though 2x memory use.

      Addendum: Can you put it on RosettaCode or let me know it's ok to put there? Everything there gets covered by the GNU FDL so I don't want to put there without some sort of permission. More code improvements are also welcome :)

        Regarding memory use: the result array footprint probably outweighs the sieve for limits up to 1014.

        Re: code. m//gogo is the sole bit of artistic liberty (or wishful thinking) and can be shortened to just //g. And sure, you're welcome to it, to work on it or repost it. An anonymonk couldn't say no, anyhow.