24891Re: [PrimeNumbers] Re: Calculate first 3.2 trillion primes in 39 hours on standard PC
- Mar 6, 2013Thank 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 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.
--- In email@example.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.
- << Previous post in topic