Thinking of a new project: Sieve of Eratosthenes

XYYXF · 2010-02-27, 21:25

Hello people :-)

While compiling the tables of the prime-counting function and its fluctuations, I realized that it's possible to set up a distributed project to sieve all the primes up to, say, 10¹⁸, and maybe further.

Tomás Oliveira e Silva used a segmented sieve and reached 1.6*10¹⁸ within ~400 CPU years. Unfortunately, Tomás recorded the prime counts only every 10¹². But these results could be used for double-checking.

I propose to save the prime counts every 10⁹. For the range of 10¹⁸ it will take 10⁹ data points. To save the space, we could record the difference

pi(x)-li(x)

multiplied by 2 (to get rid of roundoff errors) and rounded to the nearest integer. It will take just 4 bytes for each such point.

Moreover, it seems that the difference between two adjacent points never exceeds 2¹⁵ by the absolute value, so only 2 last bytes could be stored. There's an example of such a database for the range up to 10¹⁴:

http://www.primefan.ru/stuff/primes/pi.dat (200 000 bytes)

It takes only a few seconds to sieve the subrange of 5*10⁸, so, having the database, one could quickly compute the value of pi(x) for any x within the range. The database could be hosted on the web.

* * * * * *

Well, the main idea is to implement the siever which could be used by, for example, BOINC contributors. Maybe it has sense to use CUDA there? The sieving routines should be parallelizable this way, I think...

However, my programming skills are too low for this; you may just look over my simple implementation of the classical sieve up to 10¹⁵, which takes over 1 minute (!) at 1GHz for the subrange of 10⁹:
http://www.primefan.ru/stuff/soft/siever.txt

With best regards,

Andrey V. Kulsha

ET_ · 2010-02-28, 00:24

Quote:

Originally Posted by XYYXF

Hello people :-)

Andrey V. Kulsha

Hello Andrey!

You are talking about small primes, that could be proven in milliseconds.
A friend of mine wrote an assembly program for MS-DOS that calculated prime numbers in the first 2³² naturals in 3 seconds on 20 MHz machines.

The question is: is it worth it?

Who will be in charge to update 10¹⁸ values into the database?

Luigi

mdettweiler · 2010-02-28, 00:57

PrimeGrid did a project sort of like this a while back with their now-defunct "Primegen" subproject; I'm not sure what method they used or how far they got, though they hit it with enough resources that I wouldn't be surprised if they got much farther 10¹⁸.

Edit: I just checked and it seems they stopped at 640,000,000,000, which is somewhere between 2³² and 2³³. See this thread in their forum for more info.

axn · 2010-02-28, 01:07

Nobody's talking about storing primes -- only prime counts.

rogue · 2010-02-28, 01:32

I'm not understanding the usefullness of this.

XYYXF · 2010-02-28, 07:13

Quote:

Originally Posted by ET_

A friend of mine wrote an assembly program for MS-DOS that calculated prime numbers in the first 2³² naturals in 3 seconds on 20 MHz machines.

That's impossible.

Quote:

Originally Posted by ET_

Who will be in charge to update 10¹⁸ values into the database?

Where did you see 10¹⁸ values? :surprised

Quote:

Originally Posted by rogue

I'm not understanding the usefullness of this.

Quote:

Originally Posted by XYYXF

It takes only a few seconds to sieve the subrange of 5*10⁸, so, having the database, one could quickly compute the value of pi(x) for any x within the range. The database could be hosted on the web.

Random Poster · 2010-02-28, 10:32

Quote:

Originally Posted by XYYXF

It takes only a few seconds to sieve the subrange of 5*10⁸, so, having the database, one could quickly compute the value of pi(x) for any x within the range.

That seems to be an extremely slow way to compute pi(x). Best known methods are much faster, and don't require a huge database.

R. Gerbicz · 2010-02-28, 12:12

Quote:

Originally Posted by Random Poster

That seems to be an extremely slow way to compute pi(x). Best known methods are much faster, and don't require a huge database.

Then why aren't you compute pi(10^24) if it is really easy? (That would be a world record).
As far as I know Mathematica is also using precomputed table and sieve to compute pi(x).

XYYXF · 2010-02-28, 13:24

Quote:

Originally Posted by Random Poster

That seems to be an extremely slow way to compute pi(x).

Computing a single point neax x=10¹⁸ takes an hour, i.e. a thousand times slower.

Are you people really thinking that I don't understand what I propose?

rogue · 2010-02-28, 13:59

So one has a database filled with pi(x) for many values of x. Again, what is the value of that?

Mini-Geek · 2010-02-28, 15:05

http://primes.utm.edu/nthprime/ goes up to 10^12. Do you really need any more? If so, it might be helpful to take some hints on how they did it (look at "Algorithm" on that page).

Quote:

Originally Posted by XYYXF

Quote:

Originally Posted by ET_

A friend of mine wrote an assembly program for MS-DOS that calculated prime numbers in the first 2³² naturals in 3 seconds on 20 MHz machines.

That's impossible.

http://www.troubleshooters.com/codec...imenumbers.htm
On an Athlon 2400XP with 1.5GB RAM, it took 88 minutes and 41 seconds to search all numbers up to 40 billion (about 10*2^32). Guesstimating a linear scaling, it could probably do up to 2^32 in about 8-9 minutes. Not bad, but not 3 seconds on a 20 MHz machine.

2010-02-27, 21:25	#1
XYYXF Jan 2005 Minsk, Belarus 2⁴·5² Posts	Thinking of a new project: Sieve of Eratosthenes Hello people :-) While compiling the tables of the prime-counting function and its fluctuations, I realized that it's possible to set up a distributed project to sieve all the primes up to, say, 10¹⁸, and maybe further. Tomás Oliveira e Silva used a segmented sieve and reached 1.610¹⁸ within ~400 CPU years. Unfortunately, Tomás recorded the prime counts only every 10¹². But these results could be used for double-checking. I propose to save the prime counts every 10⁹. For the range of 10¹⁸ it will take 10⁹ data points. To save the space, we could record the difference pi(x)-li(x) multiplied by 2 (to get rid of roundoff errors) and rounded to the nearest integer. It will take just 4 bytes for each such point. Moreover, it seems that the difference between two adjacent points never exceeds 2¹⁵ by the absolute value, so only 2 last bytes could be stored. There's an example of such a database for the range up to 10¹⁴: http://www.primefan.ru/stuff/primes/pi.dat (200 000 bytes) It takes only a few seconds to sieve the subrange of 510⁸, so, having the database, one could quickly compute the value of pi(x) for any x within the range. The database could be hosted on the web. * * * * * * Well, the main idea is to implement the siever which could be used by, for example, BOINC contributors. Maybe it has sense to use CUDA there? The sieving routines should be parallelizable this way, I think... However, my programming skills are too low for this; you may just look over my simple implementation of the classical sieve up to 10¹⁵, which takes over 1 minute (!) at 1GHz for the subrange of 10⁹: http://www.primefan.ru/stuff/soft/siever.txt With best regards, Andrey V. Kulsha

2010-02-28, 00:57	#3
mdettweiler A Sunny Moo Aug 2007 USA (GMT-5) 3×2,083 Posts	PrimeGrid did a project sort of like this a while back with their now-defunct "Primegen" subproject; I'm not sure what method they used or how far they got, though they hit it with enough resources that I wouldn't be surprised if they got much farther 10¹⁸. Edit: I just checked and it seems they stopped at 640,000,000,000, which is somewhere between 2³² and 2³³. See this thread in their forum for more info. Last fiddled with by mdettweiler on 2010-02-28 at 01:03

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Sieve of Eratosthenes	bhelmes	Number Theory Discussion Group	43	2018-03-13 01:04
New GPU accelerated sieve of Eratosthenes	cseizert	Programming	8	2016-10-27 05:55
Sieve of Eratosthenes	Raman	Programming	4	2009-01-19 17:12
Sieve of Eratosthenes	jchein1	Homework Help	6	2007-08-27 13:51
Prime in Riesel Sieve Project	Sloth	Prime Sierpinski Project	1	2006-05-10 02:02

2010-02-28, 01:07	#4
axn Jun 2003 5,087 Posts	Nobody's talking about storing primes -- only prime counts.

2010-02-28, 01:32	#5
rogue "Mark" Apr 2003 Between here and the 2²·7·227 Posts	I'm not understanding the usefullness of this.

2010-02-28, 13:59	#10
rogue "Mark" Apr 2003 Between here and the 2²·7·227 Posts	So one has a database filled with pi(x) for many values of x. Again, what is the value of that?