Schnellster prime Test für kleine ish Zahlen

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

  •  04-10-2019
  •  | 
  •  

Frage

Ich spiele durch Projekt Euler in meiner Freizeit, und es ist bis zu dem Punkt kommen, wo ich brauche etwas Refactoring zu tun. Ich habe Miller-Rabin umgesetzt werden, sowie ein paar Siebe. Ich habe gehört, vor, dass die Siebe tatsächlich schneller für kleine ish Zahlen sind, wie in weniger als ein paar Millionen. Hat jemand irgendwelche Informationen dazu? Google war nicht sehr hilfreich.

War es hilfreich?

Lösung

Ja, werden Sie mit den meisten Algorithmen feststellen, dass Sie Raum für Zeit handeln können. Mit anderen Worten, durch die Verwendung von mehr Speichern ermöglichen, wird die Geschwindigkeit stark erhöht * a .

ich nicht wirklich wissen der Miller-Rabin-Algorithmus aber, es sei denn, es ist einfacher, als eine einzelne Shift-links / hinzufügen und Speicher-Extraktion, wird es durch eine prä- geblasen aus dem Wasser werden berechnet Sieb.

Das Wichtigste hier ist vorausberechnet. Es ist eine gute Idee, in Bezug auf Leistung, vorab berechnen Dinge wie diese, da die ersten Millionen Primzahlen wird in naher Zukunft ändern unwahrscheinlich sein: -)

Mit anderen Worten, erstellen Sie Ihr Sieb mit so etwas wie: 

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))

mit allen üblichen Warnungen über nicht Dinge wie a++ in Makros übergeben. Dies gibt Ihnen das Beste aus beiden Welten, eine blendend schnelle Nachschlagen in einer Tabelle für „small-ish“ Primzahlen, auf eine Berechnungsmethode für diejenigen, die außerhalb des Bereichs fallen zurück.

Offensichtlich würden Sie ein Programm schreiben, eine der anderen Methoden, die Lookup-Tabelle zu generieren -. Sie wollen nicht wirklich haben alles in der Hand zu geben

Aber wie bei allen Optimierungsfragen, Maßnahme nicht erraten!

* a Ein klassischer Fall dafür einige trigonometrischen Funktionen war ich einmal für ein eingebettetes System zu schreiben habe. Dies war ein kompetitiver Vertrag Gebot und das System hatte ein wenig mehr Speicherplatz als CPU Grunzen.

Wir gewannen tatsächlich den Auftrag, da unsere Eckwerte für die Funktionen der Konkurrenz weg blies.

Warum? Weil wir die Werte in einer Verweistabelle ursprünglich auf einer anderen Maschine berechnet vorzunehmen berechnet. Durch gezielten Einsatz von Reduktion (die Eingangswerte nach unten unter 90 Grad zu bringen) und trig-Eigenschaften (die Tatsache, dass Cosinus nur eine Phasenverschiebung von Sinus ist und dass die anderen drei Quadranten sind mit dem ersten zusammen), haben wir die Nachschlagetabelle nach unten zu 180 Einträge (eine pro halben Grad).

Die besten Lösungen sind diejenigen, die elegant sind und abwegig: -)

Es lohnt sich, was die folgende C-Code generiert eine solche Tabelle für Sie alle Primzahlen unter vier Millionen (283.000 von ihnen). 

#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;
}

Wenn Sie die primeTbl Tabelle zu sechzehn Millionen Einträge stoßen können (16M), werden Sie das reicht finden die prime Zahl über eine Million (die ersten 1.031.130 Primzahlen) zu halten.

Nun gibt es Möglichkeiten, das nehmen weniger Speicher wie nur Speicherung ungerade Zahlen und Einstellen des Makro machen zu kümmern, dass, oder unter Verwendung einer Bit-Maske statt unsigned Zeichen. Ich ziehe es Einfachheit der Algorithmen selbst wenn der Speicher verfügbar ist.

Andere Tipps

ich einen mehrstufigen Ansatz empfehlen. Erstens, stellen Sie sicher, es gibt keine kleinen Primfaktoren. Trial-Division durch die ersten 20 oder 30 Primzahlen funktioniert, aber wenn Sie einen cleveren Ansatz verwenden, können Sie die Anzahl der Teilungen durch die Verwendung GCDS benötigt reduzieren. Dieser Schritt filtert etwa 90% der Komposite.

Als nächstes Test, wenn die Zahl ein starker wahrscheinlich Primzahl (Miller-Rabin-Test) auf Basis 2. Diesen Schritt entfernt fast alle übrigen Komposite, aber einige seltenen Komposite passieren können.

Der letzte Proving Schritt hängt davon ab, wie groß Sie gehen möchten. Wenn Sie in einem kleinen Bereich bereit zur Arbeit sind, hat eine binäre Suche auf einer Liste von 2-Pseudoprimzahlen bis die größten Sie ermöglichen. Wenn die 2 ist ^ 32, die Liste nur 10.403 Mitglieder hat, so dass die Lookup nur 14 Abfragen nehmen sollen.

Wenn Sie auf 2 ^ 64 gehen wollen, genügt es nun (dank der Arbeit von Jan Feitisma ) zu überprüfen, ob die Zahl eine BPSW pseudoprim ist. (Sie können auch die 3 GB Liste aller Ausnahmen herunterladen, entfernen Sie diejenigen, die Probedivision entfernen würde, und schreiben Sie eine Disk-basierte binäre Suche.) T. R. Schön hat eine schöne Seite zu erklären, wie dies zu implementieren maßen effizient.

Wenn Sie höher gehen müssen, implementieren die obige Methode und verwenden Sie es als ein Unterprogramm für einen Pocklington-Stil-Test. Diese erstreckt sich die Definition von „klein-ish“; Wenn Sie weitere Informationen zu diesen Methoden wollen, fragen Sie einfach.

Als eine Variante auf dem Begriff der Vorausberechnung, können Sie zunächst billig prüfen, ob die Kandidatennummer p teilbar durch 2, 3, 5, 7 oder 11. Wenn nicht, dann p prime erklären, wenn 2 p-1 = 1 (mod p). Das wird irgendwann scheitern, aber es funktioniert auf 100 Millionen, weil ich es getestet (pre-Berechnung).

Mit anderen Worten, alle kleinen Ish Fermat pseudo-Primzahlen zur Basis 2 teilbar sind durch eine von 3, 5, 7 oder 11.

EDIT:

Wie richtig durch @starblue erwähnt, ist die oben einfach falsch. Ich hatte einen Fehler in meinem Programm. Das Beste, was ich tun kann, das ist eine Änderung oben an:

Wenn Kandidat p teilbar durch 2, 3, 5, 7 oder 11, erklären sie Verbund;
Else wenn p eines von {4181921, 4469471, 5256091, 9006401, 9863461}, erklären sie Verbund;
Else wenn p den Miller-Rabin-Test für Basen geht 2 und 5 dann erklären sie prime;
Else declare es Verbund.

Das habe ich getestet für ganze Zahlen von weniger als 10 Millionen. Vielleicht ein anderes Paar von Basen tun würde, noch besser.

Bitte akzeptieren Sie meine Entschuldigung für meine Fehler.

EDIT 2:

Nun scheint es, dass die Informationen, die ich nach war bereits auf der Wikipedia-Seite für das Miller-Rabin-Algorithmus , der Abschnitt mit dem Titel " deterministische Varianten des Tests ".

Die einzige Möglichkeit ist, sich zu Benchmark. Wenn Sie das tun, schreiben Sie es auf und schicken Sie es irgendwo online.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top