Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

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

by danaj (Friar)
on May 01, 2015 at 06:31 UTC ( #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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1125331]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (2)
As of 2022-01-17 02:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    In 2022, my preferred method to securely store passwords is:












    Results (50 votes). Check out past polls.

    Notices?