Il più veloce di prova principale per i numeri piccoli-ish

StackOverflow https://stackoverflow.com/questions/3755789

  •  04-10-2019
  •  | 
  •  

Domanda

Sto giocando attraverso il progetto di Eulero nel mio tempo libero, ed è venuto al punto in cui ho bisogno di fare un po 'di refactoring. Ho implementato Miller-Rabin, così come un paio di setacci. Ho sentito prima che i setacci sono effettivamente più veloce per i numeri piccoli-ish, come in meno di un paio di milioni. Qualcuno ha informazioni su questo? Google non è stato molto utile.

È stato utile?

Soluzione

Sì, troverete con maggior parte degli algoritmi che si possano scambiare lo spazio per il tempo. In altre parole, consentendo l'uso di più memoria, la velocità è notevolmente aumentato * a .

Io in realtà non so la Miller-Rabin algoritmo, ma, a meno che sia più semplice di un singolo shift-sinistra / aggiungere e l'estrazione della memoria, sarà saltato fuori dall'acqua da un pre setaccio calcolato.

La cosa importante qui è pre-calcolato. E 'una buona idea, in termini di prestazioni, di pre-calcolare le cose come questo in quanto il primo milione di numeri primi sarà improbabile che cambi in un prossimo futuro: -)

In altre parole, create il vostro setaccio con qualcosa di simile: 

unsigned char primeTbl[] = {0,0,1,1,0,1,0,1,0,0,0,1};
#define isPrime(x) ((x < sizeof(primeTbl) ? primeTbl[x] : isPrimeFn(x))

con tutti i soliti avvertimenti circa non passa le cose come a++ in macro. Questo ti dà il meglio di entrambi i mondi, una tabella di ricerca veloce come il fulmine per i numeri primi "piccola-ish", lasciando cadere di nuovo ad un metodo di calcolo per quelli al di fuori della gamma.

Ovviamente si dovrebbe scrivere un programma utilizzando uno degli altri metodi per generare quella tabella di ricerca -. Non si vuole veramente avere a digitare tutto in mano

Ma, come con tutte le questioni di ottimizzazione, misura, non l'indovino!

* a Un caso classico di questo è stato alcune funzioni trigonometriche una volta ho dovuto scrivere per un sistema embedded. Questo era un'offerta contrattuale competitivo e il sistema ha avuto un po 'più spazio di archiviazione di grugnito CPU.

In realtà abbiamo vinto il contratto in quanto le nostre figure di riferimento per le funzioni soffiarono via la concorrenza.

Perché? Perché abbiamo pre-calcolati i valori in una tabella di ricerca originariamente calcolato su un'altra macchina. Da uso giudizioso di riduzione (portando i valori di ingresso basso 90 gradi) e trigliceride proprietà (il fatto che coseno è solo uno sfasamento di seno e che le altre tre quadranti sono legati al primo), abbiamo ottenuto la tabella di ricerca fino a 180 voci (uno per mezzo grado).

Le soluzioni migliori sono quelli che sono elegante e subdola: -)

Per quello che vale, il seguente codice C genererà un tale tavolo per voi, tutti i numeri primi inferiori a quattro milioni (283.000 di loro). 

#include <stdio.h>

static unsigned char primeTbl[4000000];

int main (void) {
    int i, j;

    for (i = 0; i < sizeof(primeTbl); i++)
        primeTbl[i] = 1;

    primeTbl[0] = 0;
    primeTbl[1] = 0;
    for (i = 2; i < sizeof(primeTbl); i++)
        if (primeTbl[i])
            for (j = i + i; j < sizeof(primeTbl); j += i)
                primeTbl[j] = 0;

    printf ("static unsigned char primeTbl[] = {");
    for (i = 0; i < sizeof(primeTbl); i++) {
        if ((i % 50) == 0) {
            printf ("\n   ");
        }
        printf ("%d,", primeTbl[i]);
    }
    printf ("\n};\n");
    printf ("#define isPrime(x) "
        "((x < sizeof(primeTbl) ? primeTbl[x] : isPrimeFn(x))\n");

    return 0;
}

Se si può lievitare il tavolo primeTbl a sedici milioni di voci (16M), troverete che è sufficiente a mantenere il conteggio primo sopra un milione (i primi numeri primi 1,031,130).

Ora ci sono modi per fare che prendere meno di archiviazione come ad esempio memorizzare solo numeri dispari e regolando la macro per prendersi cura di questo, o utilizzando una maschera di bit al posto di caratteri senza segno. Io preferisco la semplicità di algoritmi me stesso se la memoria è disponibile.

Altri suggerimenti

Vi consiglio un approccio graduale. In primo luogo, assicurarsi che non vi siano piccoli fattori primi. Trial-dividendo per le opere prime 20 o 30 numeri primi, anche se si utilizza un approccio intelligente è possibile ridurre il numero di divisioni necessari utilizzando GCDS. Questo passaggio filtra circa il 90% dei compositi.

Avanti, prova se il numero è una forte probabilità primaria (test di Miller-Rabin) a base 2. Questo passaggio rimuove quasi tutti i restanti materiali compositi, ma alcuni compositi rari può passare.

La fase di lievitazione finale dipende da quanto grande si vuole andare. Se si è disposti a lavorare in un piccolo intervallo, fare una ricerca binaria su un elenco di 2-pseudoprimi su per la più grande si consente. Se questo è 2 ^ 32, l'elenco avrà solo 10.403 membri, in modo dalla ricerca dovrebbe prendere solo 14 interrogazioni al database.

Se si vuole andare fino a 2 ^ 64, ora basta (grazie al lavoro di Jan Feitisma ) per verificare se il numero è un pseudoprimo BPSW. (Si potrebbe anche scaricare il GB elenco di tutte le eccezioni 3, rimuovere quelli che la divisione di prova eliminerebbe, e scrivere un disco a base di ricerca binaria.) T. R. ha Bene una bella pagina che spiega come implementare questa ragionevolmente efficiente.

Se avete bisogno di andare più in alto, implementare il metodo di cui sopra e usarlo come una subroutine per un test in stile Pocklington. Questo si estende la definizione di "piccola-ish"; Se volete maggiori informazioni su questi metodi, basta chiedere.

Come variante sulla nozione di pre-calcolo, si può in primo luogo a buon mercato verificare se il candidato numero p è divisibile per 2, 3, 5, 7, o 11. Se no, allora dichiarare p primo se 2 p-1 = 1 (mod p). Questo non riuscirà ad un certo punto, ma funziona fino a 100 milioni, perché ho provato (pre-calcolo).

In altre parole, tutti i piccoli-ish Fermat pseudo-primi alla base 2 sono divisibili tra di 3, 5, 7, o 11.

EDIT:

Come correttamente rilevato dal @starblue, quanto sopra è semplicemente sbagliato. Ho avuto un bug nel mio programma. Il meglio che posso fare è modificare la precedenza a:

Se p candidato è divisibile per 2, 3, 5, 7, o 11, dichiareremo composito;
Altrimenti se p è uno dei {4.181.921, 4.469.471, 5.256.091, 9.006.401, 9.863.461}, dichiararlo composito;
Altrimenti se p supera il test di Miller-Rabin per le basi 2 e 5, allora dichiararlo prime;
dichiarare altrimenti composito.

Questo ho provato per gli interi meno di 10 milioni. Forse un paio di basi diversa farebbe ancora meglio.

La prego di accettare le mie scuse per i miei errori.

EDIT 2:

Beh, sembra che le informazioni che cercavo è già sulla pagina di Wikipedia per il Miller-Rabin algoritmo , la sezione " deterministica varianti del test ".

L'unico modo è quello di punto di riferimento se stessi. Quando si esegue, scriverlo, e pubblicarla online da qualche parte.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top