In effetti, è possibile implementare un Sieve di Atkin (SoA) illimitato senza utilizzare la segmentazione come ho fatto io here in F#. Si noti che questa è una versione puramente funzionale che non utilizza nemmeno gli array per combinare le soluzioni delle equazioni quadratiche e il filtro squaresfree e quindi è notevolmente più lento di un approccio più imperativo.
Le ottimizzazioni di Berstein che utilizzano tabelle di ricerca per intervalli di 32 bit ottimali renderebbero il codice estremamente complesso e non adatto alla presentazione, ma sarebbe piuttosto semplice adattare il codice F # in modo che le sequenze inizino a un limite inferiore impostato e vengono utilizzati solo su un intervallo per implementare una versione segmentata e/o applicare le stesse tecniche a un approccio più imperativo utilizzando gli array.
Nota che l'attuazione anche di Berstein della dichiarazione di affidabilità non è davvero più veloce del crivello di Eratostene con tutte le possibili ottimizzazioni come per Kim Walisch's primesieve, ma è solo più veloce di una versione equivalente ottimizzata del crivello di Eratostene per la gamma selezionata di numeri come da sua implementazione.
EDIT_ADD: Per coloro che non vogliono guadare attraverso pseudo-codice di Berstein e il codice C, sto aggiungendo a questa risposta per aggiungere un metodo pseudo-codice per utilizzare la dichiarazione di affidabilità in un range da basso ad alto, dove il delta da LOW a HIGH + 1 potrebbe essere vincolato a un modulo pari 60 per poter utilizzare le ottimizzazioni modulo (e potenziale bit di riempimento solo per le voci su 2,3,5).
Questo si basa su una possibile implementazione utilizzando le quadrate SoA di (4 * x^2 + y ^), (3 * x^2 + y^2) e (3 * x^2 -y^2) da esprimere come sequenze di numeri con il valore x per ogni sequenza fissata a valori compresi tra uno e SQRT ((HIGH - 1)/4), SQRT ((HIGH - 1)/3) e risoluzione del quadratico per 2 * x^2 + 2 * x - HIGH - 1 = 0 per x = (SQRT (1 + 2 * (HIGH + 1)) - 1)/2, rispettivamente, con le sequenze espresse nel mio codice F # come per il collegamento superiore . Le ottimizzazioni alle sequenze che si usano quando si setacciano solo composizioni dispari, per le sequenze "4x", i valori y devono essere solo dispari e che le sequenze "3x" necessitino solo di valori dispari di y quando x è pari e viceversa. Un'ulteriore ottimizzazione riduce il numero di soluzioni alle equazioni quadratiche (= elementi nelle sequenze) osservando che i pattern modulo sulle sequenze sopra riportate si ripetono su intervalli molto piccoli di xe ripetono anche su intervalli di y di soli 30, che viene utilizzato in il codice di Berstein ma non (ancora) implementato nel mio codice F #.
Inoltre, non includo le ottimizzazioni note che potrebbero essere applicate al primo "squares free" per utilizzare la fattorizzazione della ruota e i calcoli per l'indirizzo del segmento iniziale che utilizzo in my implementations of a segmented SoE.
Quindi ai fini del calcolo degli indirizzi di segmento di inizio sequenza per "4x", "3x +" e "3x-" (o con "3x +" e "3x-" combinati come faccio nel codice F #), e aver calcolato gli intervalli di x per ogni secondo quanto sopra, lo pseudo-codice è il seguente:
calcolare l'intervallo LOW - FIRST_ELEMENT, dove FIRST_ELEMENT è con il più basso valore applicabile di y per ogni valore dato di x oy = x - 1 per il caso della sequenza "3x-".
Per il calcolo di quanti elementi si trovano in questo intervallo, questo si riduce alla domanda di quanti di (y1)^2 + (y2)^2 + (y3)^2 ... ci sono dove ogni numero y è separato da due, per produrre "y" pari o dispari come richiesto. Come al solito nell'analisi a sequenza quadrata, osserviamo che le differenze tra i quadrati hanno un incremento crescente costante poiché in delta (9 - 1) è 8, delta (25 - 9) è 16 per un aumento di 8, delta (49 - 25) è 24 per un ulteriore aumento di 8, eccetera. in modo che per n elementi l'ultimo incremento sia 8 * n per questo esempio. Esprimendo la sequenza di elementi usando questo, capiamo che è uno (o qualunque cosa si sceglie come primo elemento) più otto volte la sequenza di qualcosa come (1 + 2 + 3 + ... + n). Ora si applica la riduzione standard delle sequenze lineari dove questa somma è (n + 1) * n/2 o n^2/2 + n/2. Questo possiamo risolvere per quanti n elementi ci sono nell'intervallo risolvendo l'equazione quadratica n^2/2 + n/2 - range = 0 o n = (SQRT (8 * range + 1) - 1)/2.
Ora, se FIRST_ELEMENT + 4 * (n + 1) * n non è uguale a LOW come indirizzo iniziale, aggiungere uno a n e utilizzare FIRST_ELEMENT + 4 * (n + 2) * (n + 1) come l'indirizzo di partenza Se si utilizzano ulteriori ottimizzazioni per applicare l'abbattimento della fattorizzazione della ruota al modello di sequenza, è possibile cercare le matrici della tabella per cercare il valore più vicino di n utilizzato che soddisfi le condizioni.
Il modulo 12 o 60 dell'elemento di avvio può essere calcolato direttamente o può essere prodotto mediante l'uso di tabelle di ricerca basate sulla natura ripetitiva delle sequenze modulo.
Ogni sequenza viene quindi utilizzata per alternare gli stati compositi fino al limite HIGH. Se la logica addizionale viene aggiunta alle sequenze per saltare i valori tra solo gli elementi applicabili per sequenza, non è necessario utilizzare ulteriormente le condizioni modulo.
Quanto sopra viene eseguito per ogni sequenza "4x" seguita dalle sequenze "3x +" e "3x-" (o si combinano "3x +" e "3x-" in un solo set di sequenze "3x") fino a i limiti x calcolati in precedenza o testati per loop.
E è fatto: dato un metodo appropriato di dividere la gamma setaccio in segmenti, che è meglio utilizzato come dimensioni fisse che sono legati alle dimensioni della cache CPU per migliore efficienza accesso alla memoria, un metodo di segmentazione il SoA usato da Bernstein ma un po 'più semplice nell'espressione come menziona ma non combina le operazioni di modulo e il bit di compressione.
Ho studiato il setaccio Atkin/Bernstein per anni e non ho mai capito come renderlo segmentato - con questo intendo, avviarlo in un numero arbitrariamente grande, con forse un po 'più piccolo di precomputazione. Sarei interessato a vedere se qualcuno ha. – librik