mersenneforum.org listing 15-digit primes
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2009-10-19, 13:25 #1 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 644410 Posts 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?)
2009-10-19, 14:37   #2
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by fivemack 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.

2009-10-19, 14:40   #3
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by R.D. Silverman 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.

2009-10-19, 15:25   #4
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

22·32·179 Posts

Quote:
 Originally Posted by R.D. Silverman 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) ...

 2009-10-19, 15:54 #5 garo     Aug 2002 Termonfeckin, IE 22×691 Posts You may want to look at this page for ideas: http://www.troubleshooters.com/codec...imenumbers.htm
2009-10-19, 18:25   #6
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 Originally Posted by fivemack 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.

2009-10-19, 18:35   #7
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102568 Posts

Quote:
 Originally Posted by R.D. Silverman 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

2009-10-19, 18:41   #8
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 Originally Posted by Mini-Geek so I guess anything only storing one byte per diff just has that limit.
Yep.

 2009-10-19, 20:22 #9 CRGreathouse     Aug 2006 175B16 Posts 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.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post davar55 Puzzles 13 2018-03-15 14:46 RienS Miscellaneous Math 15 2014-11-18 01:48 Stargate38 Puzzles 4 2011-07-14 12:16 petrw1 Puzzles 10 2009-12-16 21:58 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.