Databases
StackOverflow2013
Postsdbo
POWhere does the limitation of 10^15 in D.J. Bernstein's 'primegen' program come from?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhere does the limitation of 10^15 in D.J. Bernstein's 'primegen' program come from?
    text
    copied!<p>At <a href="http://cr.yp.to/primegen.html" rel="nofollow">http://cr.yp.to/primegen.html</a> you can find sources of program that uses Atkin's sieve to generate primes. As the author says that it may take few months to answer an e-mail sent to him (I understand that, he sure is an occupied man!) I'm posting this question.</p> <p>The page states that 'primegen can generate primes up to 1000000000000000'. I am trying to understand why it is so. There is of course a limitation up to 2^64 ~ 2 * 10^19 (size of long unsigned int) because this is how the numbers are represented. I know for sure that if there would be a huge prime gap (> 2^31) then printing of numbers would fail. However in this range I think there is no such prime gap.</p> <p>Either the author overestimated the bound (and really it is around 10^19) or there is a place in the source code where the arithmetic operation can overflow or something like that.</p> <p>The funny thing is that you actually MAY run it for numbers > 10^15:</p> <pre><code>./primes 10000000000000000 10000000000000100 10000000000000061 10000000000000069 10000000000000079 10000000000000099 </code></pre> <p>and if you believe Wolfram Alpha, it is correct.</p> <p>Some facts I had "reverse-engineered":</p> <ol> <li>numbers are sifted in batches of 1,920 * PRIMEGEN_WORDS = 3,932,160 numbers (see primegen_fill function in primegen_next.c)</li> <li>PRIMEGEN_WORDS controls how big a single sifting is - you can adjust it in primegen_impl.h to fit your CPU cache,</li> <li>the implementation of the sieve itself is in primegen.c file - I assume it is correct; what you get is a bitmask of primes in pg->buf (see primegen_fill function)</li> <li>The bitmask is analyzed and primes are stored in pg->p array.</li> </ol> <p>I see no point where the overflow may happen. </p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload