Re: [PrimeNumbers] Calculate first 3.2 trillion primes in 39 hours on standard PC

Expand Messages
• Thanks Jack, I ll take a look. RAM becomes an issue in my implementation at least because as x gets large then if the sieve slice is too small one wastes
Message 1 of 7 , Mar 4, 2013
• 0 Attachment
Thanks Jack, I'll take a look.

RAM becomes an issue in my implementation at least because as x gets large then if the sieve 'slice' is too small one wastes cycles looping through values of iy where there are no values of ix in range (ix, iy being cartesians on the sieve grid).

Increase sieve slice size removes waste and improves efficiency by manyfold.

I created a Javascript visualisation here:
http://www.daltonfirth.co.uk/tuts/js/prime-finder/prime-finder.html

jdf

[Non-text portions of this message have been removed]
• ... I think the results of a willy-waving contest nearly a decade ago between Terje Mathisen and James Van Buskirk on c.l.a.x, concluded that about an order of
Message 2 of 7 , Mar 5, 2013
• 0 Attachment
Jack Brennen wrote:
> Looks like you can extrapolate that implementation to get the first
> 3.2 trillion primes in about 5-6 hours on an Intel i7-920, assuming
> sufficient RAM available.

I think the results of a willy-waving contest nearly a decade ago between Terje Mathisen and James Van Buskirk on c.l.a.x, concluded that about an order of magnitude faster than that speed should be possible. If you're James, that is. Tomas e Silva's sieve uses pretty much the same algorithm, but he hasn't optimised it quite as much. (James is an extreme optimiser, very few people can optimise as much!)
http://www.ieeta.pt/~tos/software/prime_sieve.html

Phil
• ... 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
Message 3 of 7 , Mar 6, 2013
• 0 Attachment
--- In primenumbers@yahoogroups.com, Phil Carmody <thefatphil@...> wrote:
>
> Jack Brennen wrote:
> > Looks like you can extrapolate that implementation to get the first
> > 3.2 trillion primes in about 5-6 hours on an Intel i7-920, assuming
> > sufficient RAM available.
>
> I think the results of a willy-waving contest nearly a decade ago between Terje Mathisen and James Van Buskirk on c.l.a.x, concluded that about an order of magnitude faster than that speed should be possible. If you're James, that is. Tomas e Silva's sieve uses pretty much the same algorithm, but he hasn't optimised it quite as much. (James is an extreme optimiser, very few people can optimise as much!)
> http://www.ieeta.pt/~tos/software/prime_sieve.html
>
> Phil
>

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
Message 4 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 5 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.