## Re: Calculate first 3.2 trillion primes in 39 hours on standard PC

Expand Messages
• ... Apologies, I was confusing pi(1e14) ~= 3.2e12 with pi(3.2e12). After running some experiments, it looks like the two programs I mentioned will take about
Message 1 of 7 , Mar 6, 2013
• 0 Attachment
--- In primenumbers@yahoogroups.com, "Ben Buhrow" <bbuhrow@...> wrote:

>
> Nearly two orders of magnitude is possible. YAFU and primesieve both compute pi(x) to 3.2e12 using the sieve of Eratosthenes in about 30 minutes on my machine (a pretty fast server). They are both threadable too - with 4 threads YAFU takes about 8 minutes.
>
> - ben.
>

Apologies, I was confusing pi(1e14) ~= 3.2e12 with pi(3.2e12). After running some experiments, it looks like the two programs I mentioned will take about 18 hrs for pi(1e14), so more like a factor of 2.
• Thank you Ben. I have already optimised down to 18 hours for pi(1e14) however primesieve is consistently running at least 4 times faster on my machine. I am
Message 2 of 7 , Mar 6, 2013
• 0 Attachment
Thank you Ben.

I have already optimised down to 18 hours for pi(1e14) however primesieve is consistently running at least 4 times faster on my machine.

I am aware that I might be using an odd method to stitch together my sieve segments.  Some Javascript here (when you click on the demo link) explains how I have calculated my boundaries:
http://www.daltonfirth.co.uk/tuts/js/prime-finder/prime-finder.html

I am not seeing the efficiency improvements the primesieve author gets when the sieve memory fits into the L2 cache; I will probably have to switch to Tomás Oliveira e Silva's bucket method.

I had a hunch my method, which allows starting on a prime's square for starting values greater than seg_start/start_val, might be efficient, but alas...

I might try improving the storage compression, I'm currently using modulo 30, but I doubt I'll find another 4x optimisation in my code.

JDF

--- In primenumbers@yahoogroups.com, "Ben Buhrow"  wrote:

>
> Nearly two orders of magnitude is possible.  YAFU and primesieve both compute pi(x) to 3.2e12 using the sieve of Eratosthenes in about 30 minutes on my machine (a pretty fast server).  They are both threadable too - with 4 threads YAFU takes about 8 minutes.
>
> - ben.
>

Apologies, I was confusing pi(1e14) ~= 3.2e12 with pi(3.2e12).  After running some experiments, it looks like the two programs I mentioned will take about 18 hrs for pi(1e14), so more like a factor of 2.
Your message has been successfully submitted and would be delivered to recipients shortly.