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;
    }
}

    [download]
    Pure perl isn't up to warp-speed, understandably.

[reply]
[d/l]
[select]

      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 :)

[reply]

        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.

[reply]
[d/l]
[select]

In Section Cool Uses for Perl