mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2010-02-27, 21:25   #1
XYYXF
 
XYYXF's Avatar
 
Jan 2005
Minsk, Belarus

24×52 Posts
Default 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, 1018, and maybe further.

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

I propose to save the prime counts every 109. For the range of 1018 it will take 109 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 215 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 1014:

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

It takes only a few seconds to sieve the subrange of 5*108, 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 1015, which takes over 1 minute (!) at 1GHz for the subrange of 109:
http://www.primefan.ru/stuff/soft/siever.txt

With best regards,

Andrey V. Kulsha
XYYXF is offline   Reply With Quote
Old 2010-02-28, 00:24   #2
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2×3×5×7×23 Posts
Default

Quote:
Originally Posted by XYYXF View Post
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 232 naturals in 3 seconds on 20 MHz machines.

The question is: is it worth it?

Who will be in charge to update 1018 values into the database?

Luigi
ET_ is offline   Reply With Quote
Old 2010-02-28, 00:57   #3
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

624910 Posts
Default

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 1018.

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

Last fiddled with by mdettweiler on 2010-02-28 at 01:03
mdettweiler is offline   Reply With Quote
Old 2010-02-28, 01:07   #4
axn
 
axn's Avatar
 
Jun 2003

3×17×101 Posts
Default

Nobody's talking about storing primes -- only prime counts.
axn is online now   Reply With Quote
Old 2010-02-28, 01:32   #5
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

144428 Posts
Default

I'm not understanding the usefullness of this.
rogue is offline   Reply With Quote
Old 2010-02-28, 07:13   #6
XYYXF
 
XYYXF's Avatar
 
Jan 2005
Minsk, Belarus

19016 Posts
Default

Quote:
Originally Posted by ET_ View Post
A friend of mine wrote an assembly program for MS-DOS that calculated prime numbers in the first 232 naturals in 3 seconds on 20 MHz machines.
That's impossible.

Quote:
Originally Posted by ET_ View Post
Who will be in charge to update 1018 values into the database?
Where did you see 1018 values? :surprised

Quote:
Originally Posted by rogue View Post
I'm not understanding the usefullness of this.
Quote:
Originally Posted by XYYXF View Post
It takes only a few seconds to sieve the subrange of 5*108, 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.

Last fiddled with by XYYXF on 2010-02-28 at 08:06
XYYXF is offline   Reply With Quote
Old 2010-02-28, 10:32   #7
Random Poster
 
Random Poster's Avatar
 
Dec 2008

179 Posts
Default

Quote:
Originally Posted by XYYXF View Post
It takes only a few seconds to sieve the subrange of 5*108, 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.
Random Poster is offline   Reply With Quote
Old 2010-02-28, 12:12   #8
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×32×83 Posts
Default

Quote:
Originally Posted by Random Poster View Post
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).
R. Gerbicz is offline   Reply With Quote
Old 2010-02-28, 13:24   #9
XYYXF
 
XYYXF's Avatar
 
Jan 2005
Minsk, Belarus

24·52 Posts
Default

Quote:
Originally Posted by Random Poster View Post
That seems to be an extremely slow way to compute pi(x).
Computing a single point neax x=1018 takes an hour, i.e. a thousand times slower.

Are you people really thinking that I don't understand what I propose?
XYYXF is offline   Reply With Quote
Old 2010-02-28, 13:59   #10
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2·3,217 Posts
Default

So one has a database filled with pi(x) for many values of x. Again, what is the value of that?
rogue is offline   Reply With Quote
Old 2010-02-28, 15:05   #11
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

22×11×97 Posts
Default

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 View Post
Quote:
Originally Posted by ET_ View Post
A friend of mine wrote an assembly program for MS-DOS that calculated prime numbers in the first 232 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.

Last fiddled with by Mini-Geek on 2010-02-28 at 15:05
Mini-Geek is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 11:39.


Mon Oct 25 11:39:16 UTC 2021 up 94 days, 6:08, 0 users, load averages: 0.95, 1.00, 0.95

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.