Dove si trova la limitazione di 10^15 in D.J. Il programma "primegen" di Bernstein viene da?

Question

A http://cr.yp.to/primegen.html è possibile trovare le fonti del programma che utilizza il setaccio di Atkin per generare i primi. Come dice l'autore, potrebbero essere necessari alcuni mesi per rispondere a una e-mail inviata a lui (capisco che è sicuramente un uomo occupato!) Sto postando questa domanda.

La pagina indica che 'primegen può generare numeri primi fino a 1000000000000000'. Sto cercando di capire perché è così. Esiste naturalmente una limitazione fino a 2^64 ~ 2 * 10^19 (dimensione int lunga non firmata) perché questo è il modo in cui i numeri sono rappresentati. So per certo che se ci fosse un enorme vuoto principale (> 2^31), la stampa dei numeri fallirebbe. Tuttavia, in questo intervallo, penso che non ci sia un divario così grande.

O l'autore ha sovrastimato il limite (e in realtà è intorno a 10^19) o c'è un posto nel codice sorgente in cui l'operazione aritmetica può traboccare o qualcosa del genere.

La cosa divertente è che in realtà può essere eseguito per i numeri> 10^15:

./primes 10000000000000000 10000000000000100 
10000000000000061 
10000000000000069 
10000000000000079 
10000000000000099 

e se si crede Wolfram Alpha, che sia corretto.

Alcuni fatti che avevano "reverse-engineered":

1. numeri vengono setacciati in lotti di 1.920 * PRIMEGEN_WORDS = 3.932.160 numeri (vedi funzione primegen_fill in primegen_next.c)
2. PRIMEGEN_WORDS controlli quanto è grande un singolo il setacciamento è - è possibile regolarlo in primegen_impl.h per adattarlo alla cache della CPU,
3. l'implementazione del setaccio stesso è nel file primegen.c - presumo sia corretto; quello che ottieni è una maschera di bit di primi in pg-> buf (vedi funzione primegen_fill)
4. La maschera di bit viene analizzata e i primi vengono memorizzati in pg-> p array.

vedo nessun punto in cui l'overflow può accadere.

Answer 1

Vorrei essere sul mio computer per guardare, ma ho il sospetto che avresti avuto un successo diverso se avessi iniziato a 1 come limite inferiore.

Answer 2

Giusto dall'algoritmo, concluderei che il limite superiore deriva dai numeri a 32 bit. La pagina menziona Pentium-III come CPU, quindi suppongo che sia molto vecchia e non usi 64 bit.

2^32 sono circa 10^9. Setaccio di Atkins (che l'algoritmo usa) richiede N^(1/2) bit (usa un grande bitfield). Il che significa che nella memoria grande 2^32 puoi creare (conservativo) N circa 10^15. Dato che questo numero è un limite superiore conservativo approssimativo (avete il sistema e altri programmi che occupano memoria, riservando intervalli di indirizzi per IO, ...) il limite superiore reale è/potrebbe essere più alto.