Memorizzazione efficiente di numeri primi

Question

Per una libreria, ho bisogno di memorizzare i primi numeri primi fino a un limite L. Questa raccolta deve avere un tempo di ricerca O (1) (per verificare se un numero è primo o no) e deve essere facile, dato un numero, per trovare il prossimo numero primo (supponendo che sia più piccolo di L).

Dato che L è fisso, un setaccio Eratostene per generare l'elenco va bene. In questo momento, utilizzo un array booleano compresso per memorizzare l'elenco, che contiene solo voci per numeri dispari compresi tra 3 e L (inclusi). Questo richiede (L-2)/2 bit di memoria. Mi piacerebbe essere in grado di aumentare staticamente L senza usare più memoria.

Esiste una struttura dati che utilizza meno memoria con proprietà simili? O almeno con il tempo di ricerca costante? (Numeri dispari possono poi essere enumerati finché non avremo un numero primo)

(la lingua che ho scritto questo è Factor ma la questione sarebbe lo stesso in qualsiasi lingua che si è incorporato o matrici di bit compressi facilmente programmabili)

Answer 1

È possibile controllare in modo esplicito più numeri primi per rimuovere la ridondanza.

Al momento si esegue questa operazione solo per due, controllando la divisibilità per due in modo esplicito e quindi memorizzando solo i numeri dispari se sono primi.

Per 2 e 3 si ottiene resto da 0 a 5, di cui solo 1 e 5 non sono divisibili per due o tre e possono portare a un numero primo, quindi si scende a 1/3.

Per 2, 3 e 5 si ottengono 8 numeri su 30, che è bello memorizzare in un byte.

Questo è spiegato in dettaglio here.

Answer 2

Se riesci a capire quali sono Mersenne o altri numeri primi facilmente rappresentati, potresti essere in grado di salvare alcuni bit usando quella rappresentazione con un flag per i numeri applicabili.

Inoltre, che ne dici di memorizzare i numeri come differenza rispetto al numero precedente? Quindi la dimensione non dovrebbe aumentare altrettanto velocemente (ma la ricerca sarebbe lenta). Combinando con l'approccio di cui sopra, è possibile memorizzare i numeri primi di Mersenne e la differenza rispetto all'ultimo primo di Mersenne.

Answer 3

Dato che la memoria è così a buon mercato, non penso che tu possa fare molto meglio da una prospettiva di velocità del tuo schema esistente.

Se c'è una soluzione migliore, quindi mi piacerebbe pensare che sarebbe approfittare della Prime Number Theorem che mostra che, come L diventa più grande, il limite di

π (L)/(L/ln (L)) approcci 1.

Forse una soluzione migliore avrebbe una soluzione di imballaggio adattiva in una struttura di dati del tipo skip list.

Answer 4

Forse una struttura dati trie che contiene solo i numeri primi è ciò che stai cercando. Invece di usare caratteri come indici, potresti usare le cifre intere. Una implementazione di questo è Judy-Array s.

Anche se non soddisfano i requisiti O (1), sono estremamente efficienti in termini di memoria per chiavi simili (come la maggior parte dei numeri) e abbastanza veloci da cercare con un O (m) (m = tasto -lunghezza) al massimo.

Se si ricerca un primo nell'albero pre-generato, è possibile percorrere l'albero fino a quando non lo si trova o si è già nel nodo che si trova accanto al primo e al successivo primo.

Answer 5

Al momento si sta trattando 2 come caso speciale e quindi si dispone di un array in cui ogni numero dispari è mappato su un elemento nell'array (con alcuni numeri dispari primi). Potresti migliorare su questo trattando 2 e 3 come casi speciali riconoscendo che il resto dei numeri primi sono nella forma 6n + 1 o 6n-1 (cioè per tutti i primi p dove p> 3, p mod 6 = 1 o 5). Questo può essere ulteriormente generalizzato - vedi Wikipedia. Per tutti i numeri primi p> 5, p mod 30 = 1, 7, 11, 13, 17, 19, 23 o 29. Puoi continuare con questo e ridurre la memoria necessaria a scapito del tempo di elaborazione (anche se sarà ancora O (1), solo un O più lento (1)).

Answer 6

Come su una specie di tabella hash?

si avrebbe bisogno di una buona funzione di hash (qualcosa come n mod p, dove p non è un multiplo di uno qualsiasi dei numeri primi q prezzo - scegliere q sufficientemente elevato, al fine di ridurre al minimo il numero di collisioni).

Answer 7

Un'alternativa alle bitmap e alle ruote compresse, ma ugualmente efficiente in determinati contesti, sta memorizzando le differenze tra numeri primi consecutivi. Se si omette il numero 2 come al solito, tutte le differenze sono pari. Memorizzazione differenza/2 è possibile ottenere fino a 2^40ish regioni (poco prima di 1999066711391) utilizzando variabili di dimensioni pari a byte.

I primi su 2^32 richiedono solo 194 MByte, rispetto ai 256 MByte per una bitmap con solo dispari. L'iterazione su numeri primi delta-memorizzati è molto più veloce rispetto a quella con memoria a ruote, che include la ruota modulo-2 nota come bitmap odds-only.

Per intervalli da 1999066711391 in poi, sono necessarie dimensioni di cella più grandi o memorizzazione di lunghezza variabile. Quest'ultimo può essere estremamente efficiente anche se si utilizzano schemi molto semplici (ad esempio, continuare ad aggiungere fino a un byte < 255, come nella compressione dello stile LZ4), a causa della frequenza estremamente bassa di spazi vuoti più lunghi di 510/2.

Per motivi di efficienza è meglio dividere l'intervallo in sezioni (pagine) e gestirle in stile B-Tree.

La codifica delle entropie delle differenze (codifica Huffmann o aritmetica) riduce i requisiti di memorizzazione permanente a meno della metà, che è vicino all'ottimale teorico e migliore degli elenchi o delle ruote compressi utilizzando i migliori packer disponibili.

Se i dati sono memorizzati non compressi, è ancora molto più compatto dei file di numeri binari o testuali, di un ordine di grandezza o superiore. Con un indice di stile B-Tree in atto, è facile mappare semplicemente le sezioni in memoria secondo necessità e scorrere su di esse a velocità incredibile.

Answer 8

Controllare il tutorial TopCoder su numeri primi: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=math_for_topcoders

Answer 9

Come su un albero di Interval? http://www.geeksforgeeks.org/interval-tree/

Potrebbe non essere O (1) ma è molto veloce. Come forse O (log (p (n))) dove p (n) è il numero di numeri primi fino al numero n. In questo modo, la memoria di cui avrai bisogno sarà proporzionale al numero di primi, riducendo notevolmente i costi di memoria.Ad esempio, supponiamo di trovare un primo a p1 e poi il successivo a p2, Inserisci intervallo (p1, p2) e così via e quando esegui una ricerca per qualsiasi numero in quell'intervallo restituirà questo intervallo e puoi restituire p2 quale sarebbe la risposta nel tuo caso.