mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2009-10-19, 13:25   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

644410 Posts
Default listing 15-digit primes

What's the current state of the art in software for listing the primes in medium-sized intervals a reasonable way along the number line (say 10^14-10^9 .. 10^14) on a CPU?

Also, if I've gone to the bother of writing a very fast CUDA routine for listing large primes, are there any interesting number-theoretical things to _do_ with the large primes? I suppose a wise person would have asked this before writing the routine, but never have I called myself a wise person.

(would it be interesting to try to write some CUDA code for sieving Sierpinski numbers or similar?)
fivemack is offline   Reply With Quote
Old 2009-10-19, 14:37   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by fivemack View Post
What's the current state of the art in software for listing the primes in medium-sized intervals a reasonable way along the number line (say 10^14-10^9 .. 10^14) on a CPU?
What do you mean by "list"? Store on disk? Is compactness of the
representation important? (e.g. one can 'list' all the primes in an interval
of length 10 using just 4 bits).

Finding the primes in such an interval is best done by a simple Sieve
or Eratosthenes.

Quote:

Also, if I've gone to the bother of writing a very fast CUDA routine for listing large primes, are there any interesting number-theoretical things to _do_ with the large primes?
-- Construct pseudo RNGs. Whether this is 'interesting' depends upon
one's viewpoint.

-- Help out in Goldbach computations.

There really are not many uses for lists of large primes.
R.D. Silverman is offline   Reply With Quote
Old 2009-10-19, 14:40   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
What do you mean by "list"? Store on disk? Is compactness of the
representation important? (e.g. one can 'list' all the primes in an interval
of length 10 using just 4 bits).

Finding the primes in such an interval is best done by a simple Sieve
or Eratosthenes.



-- Construct pseudo RNGs. Whether this is 'interesting' depends upon
one's viewpoint.

-- Help out in Goldbach computations.

There really are not many uses for lists of large primes.
Note that implementing Brent's sub-linear sieve might be
useful, but it depends on the size of the primes and the length of the
interval. There is a fair amount of pre-computation overhead.
R.D. Silverman is offline   Reply With Quote
Old 2009-10-19, 15:25   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

22·32·179 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
What do you mean by "list"? Store on disk? Is compactness of the
representation important? (e.g. one can 'list' all the primes in an interval
of length 10 using just 4 bits).

Finding the primes in such an interval is best done by a simple Sieve
of Eratosthenes.
With respect, I would say that finding the primes in such an interval is (probably) best done by a sophisticated implementation of the sieve of Eratosthenes; the question of when to move from checking each entry in the array for divisibility by small primes, by techniques similar to texture mapping, to randomly writing to the array in the positions corresponding to the large primes, perhaps with bucketting techniques, gets less trivial the more I work on it.

The Goldbach testing is up to 1.5e18, which needs about a 64MB array to store the small primes (one byte per difference) ...
fivemack is offline   Reply With Quote
Old 2009-10-19, 15:54   #5
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

22×691 Posts
Default

You may want to look at this page for ideas:

http://www.troubleshooters.com/codec...imenumbers.htm
garo is offline   Reply With Quote
Old 2009-10-19, 18:25   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by fivemack View Post
With respect, I would say that finding the primes in such an interval is (probably) best done by a sophisticated implementation of the sieve of Eratosthenes; the question of when to move from checking each entry in the array for divisibility by small primes, by techniques similar to texture mapping, to randomly writing to the array in the positions corresponding to the large primes, perhaps with bucketting techniques, gets less trivial the more I work on it.

The Goldbach testing is up to 1.5e18, which needs about a 64MB array to store the small primes (one byte per difference) ...
I meant that the *algorithm* is simple. Of course one can (and should) do
a sophisticated implementation. I separate the two.

BTW, one stores HALF the distance, not the distance itself, since it is
always even.
R.D. Silverman is offline   Reply With Quote
Old 2009-10-19, 18:35   #7
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102568 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I meant that the *algorithm* is simple. Of course one can (and should) do
a sophisticated implementation. I separate the two.

BTW, one stores HALF the distance, not the distance itself, since it is
always even.
What do you do when the gap is above 512 (which is double the amount you can store in one byte)? The first such occurrence is after a 12-digit prime (304599508537), so this won't really cause any problems until you're searching around 24 digits...so I guess anything only storing one byte per diff just has that limit.

Last fiddled with by Mini-Geek on 2009-10-19 at 18:37
Mini-Geek is offline   Reply With Quote
Old 2009-10-19, 18:41   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
so I guess anything only storing one byte per diff just has that limit.
Yep.
R.D. Silverman is offline   Reply With Quote
Old 2009-10-19, 20:22   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

175B16 Posts
Default

I suppose once you run out of space you just move to two bytes. That shouldn't be exhausted until > 10^157 if you believe Cramér.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Digit strings containing primes davar55 Puzzles 13 2018-03-15 14:46
What to do with 16 digit twin, non-Mersenne primes? RienS Miscellaneous Math 15 2014-11-18 01:48
911 Digit Primes Quiz Stargate38 Puzzles 4 2011-07-14 12:16
Prime-Digit Primes... petrw1 Puzzles 10 2009-12-16 21:58
Twin primes in the 50,000 digit range? Joshua2 Math 15 2005-06-11 18:46

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


Tue Dec 7 09:11:11 UTC 2021 up 137 days, 3:40, 0 users, load averages: 1.25, 1.53, 1.49

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.