Schnellster Primzahltest für kleine Zahlen

Ich spiele in meiner Freizeit das Projekt Euler durch, und es ist an dem Punkt angelangt, an dem ich etwas umgestalten muss. Ich habe Miller-Rabin sowie einige Siebe implementiert. Ich habe schon einmal gehört, dass Siebe bei kleinen Zahlen, wie bei weniger als ein paar Millionen, tatsächlich schneller sind. Hat jemand Informationen dazu? Google war nicht sehr hilfreich.

Lösung des Problems

Ja, Sie werden bei den meisten Algorithmen feststellen, dass Sie Raum gegen Zeit eintauschen können. Mit anderen Worten, durch die Verwendung von mehr Speicher wird die Geschwindigkeit stark erhöht *a.

Ich kenne den Miller-Rabin-Algorithmus nicht wirklich, aber wenn er nicht einfacher ist als eine einzelne Verschiebung nach links / Add und Speicherextraktion, wird er von einem vorberechneten Sieb aus dem Wasser geblasen.

Das Wichtigste hier ist vorberechnet. Es ist in Bezug auf die Leistung eine gute Idee, solche Dinge im Voraus zu berechnen, da sich die erste Million Primzahlen in naher Zukunft wahrscheinlich nicht ändern werden:-)

Mit anderen Worten, erstellen Sie Ihr Sieb mit 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 all den üblichen Vorbehalten, Dinge nicht wie a++in Makros zu übergeben. Dies gibt Ihnen das Beste aus beiden Welten, eine blitzschnelle Tabellensuche für "kleine" Primzahlen, die auf eine Berechnungsmethode für diejenigen außerhalb des Bereichs zurückfällt.

Offensichtlich würden Sie ein Programm schreiben, das eine der anderen Methoden verwendet, um diese Nachschlagetabelle zu generieren - Sie möchten nicht wirklich alles von Hand eingeben müssen.

Aber wie bei allen Optimierungsfragen: Messen, nicht raten!

*a Ein klassischer Fall dafür waren einige Triggerfunktionen, die ich einmal für ein eingebettetes System schreiben musste. Dies war ein konkurrenzfähiges Vertragsangebot und das System hatte etwas mehr Speicher als CPU-Grunzen.

Wir haben den Auftrag tatsächlich gewonnen, da unsere Eckwerte für die Funktionen die Konkurrenz umgehauen haben.

Wieso den? Weil wir die Werte in eine Lookup-Tabelle vorberechnet haben, die ursprünglich auf einer anderen Maschine berechnet wurde. Durch den vernünftigen Einsatz von Reduktion (die Eingabewerte unter 90 Grad bringen) und trigonometrischen Eigenschaften (die Tatsache, dass der Kosinus nur eine Phasenverschiebung des Sinus ist und dass die anderen drei Quadranten mit dem ersten zusammenhängen) haben wir die Nachschlagetabelle heruntergefahren 180 Einträge (einer pro Halbgrad).

Die besten Lösungen sind die, die elegant und hinterhältig sind:-)

Für das, was es wert ist, generiert der folgende C-Code eine solche Tabelle für Sie, alle Primzahlen unter vier Millionen (283.000 davon).

#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 primeTblTabelle auf sechzehn Millionen Einträge (16 Millionen) aufstocken können, werden Sie feststellen, dass dies ausreicht, um die Primzahl über einer Million zu halten (die ersten 1.031.130 Primzahlen).

Jetzt gibt es Möglichkeiten, dafür zu sorgen, dass weniger Speicherplatz benötigt wird, z. B. nur ungerade Zahlen zu speichern und das Makro entsprechend anzupassen oder eine Bitmaske anstelle von Zeichen ohne Vorzeichen zu verwenden. Ich selbst bevorzuge die Einfachheit der Algorithmen, wenn der Speicher verfügbar ist.