Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

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

by Anonymous Monk
on May 02, 2015 at 17:20 UTC ( [id://1125458]=note: print w/replies, xml ) Need Help??


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

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.

Replies are listed 'Best First'.
Re^7: Number functions.. primes (ugly code runs faster)
by danaj (Friar) on May 07, 2015 at 23:54 UTC

    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.

        On memory footprint, it's important if using it for just the count where there is no array. Also for cases where we hold onto the string for later use in walking primes without resieving or storing the array. However, even doubling the string memory still results in >10x less memory than the array versions.

        Thanks re posting. Given the licensing, I thought it was prudent to ask.

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others taking refuge in the Monastery: (4)
As of 2024-03-28 21:15 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found