Gibt es clevere Algorithmen für die Berechnung hochwertiger Prüfsummen für Millionen oder Milliarden von Primzahlen? Das heißt mit maximaler Fehlererkennungsfähigkeit und vielleicht segmentierbar?

Motivation

Kleine Primzahlen - bis zu 64 Bit groß - können bei Bedarf mit Millionen pro Sekunde gesiebt werden, indem eine kleine Bitmap zum Sieben potenzieller Faktoren (bis zu 2 ^ 32-1) und eine zweite Bitmap zum Sieben der Zahlen verwendet werden im Zielbereich.

Algorithmus und Implementierung sind relativ einfach und unkompliziert, aber der Teufel steckt im Detail: Werte tendieren dazu, die Grenzen integrierter Integraltypen überall zu überschreiten oder zu überschreiten, Grenzfälle gibt es (sozusagen) und sogar Unterschiede in der Gleitkommastärke können auftreten Fehler verursachen, wenn die Programmierung nicht ausreichend defensiv ist. Ganz zu schweigen von dem Chaos, das ein optimierender Compiler selbst bei bereits kompiliertem, bereits getestetem Code in einer statischen Bibliothek anrichten kann (wenn die Link-Time-Code-Generierung verwendet wird). Ganz zu schweigen davon, dass schnellere Algorithmen in der Regel viel komplizierter und damit noch spröder sind.

Dies hat zwei Konsequenzen: Testergebnisse sind grundsätzlich bedeutungslos, es sei denn, die Tests werden mit dem endgültigen ausführbaren Image durchgeführt, und es ist äußerst wünschenswert, den ordnungsgemäßen Betrieb zur Laufzeit während der normalen Verwendung zu überprüfen.

Überprüfen gegen vorberechnete Werte würde das höchste Maß an Vertrauen geben, aber die erforderlichen Dateien sind groß und klobig. Eine Textdatei mit 10 Millionen Primzahlen ist in der Größenordnung von 100 MB unkomprimiert und mehr als 10 MB komprimiert. Das Speichern von bytekodierten Differenzen erfordert ein Byte pro Primzahl, und die Entropiekodierung kann die Größe bestenfalls auf die Hälfte reduzieren (5 MB für 10 Millionen Primzahlen). Daher würde selbst eine Datei, die nur die kleinen Faktoren bis zu 2 ^ 32 abdeckt, ungefähr 100 MB wiegen, und die Komplexität des Decoders würde die des Fenstersiebs selbst übersteige

Dies bedeutet, dass das Prüfen anhand von Dateien nur als endgültige Freigabeprüfung für eine neu erstellte ausführbare Datei möglich ist. Ganz zu schweigen davon, dass die vertrauenswürdigen Dateien nicht einfach zu bekommen sind. DasPrime Pages Angebot Dateien für die ersten 50 Millionen Primzahlen, und sogar die erstaunlichen primos.mat.br geht nur bis zu 1.000.000.000.000. Dies ist bedauerlich, da viele der Grenzfälle (== Testbedarf) zwischen 2 ^ 62 und 2 ^ 64-1 auftreten.

Dies hinterlässt eine Prüfsumme. Auf diese Weise wäre der Platzbedarf gering und nur proportional zur Anzahl der Testfälle. Ich möchte nicht, dass eine anständige Prüfsumme wie MD5 oder SHA-256 verfügbar ist, und da die Zielnummern alle Primzahlen sind, sollte es möglich sein, mit einigen einfachen Operationen auf den Zahlen eine qualitativ hochwertige, hochauflösende Prüfsumme zu generieren sich

Das habe ich mir bisher ausgedacht. Der Raw Digest besteht aus vier 64-Bit-Zahlen. am ende kann es auf die gewünschte größe heruntergeklappt werden.

   for (unsigned i = 0; i < ELEMENTS(primes); ++i)
   {
      digest[0] *= primes[i];              // running product (must be initialised to 1)
      digest[1] += digest[0];              // sum of sequence of running products
      digest[2] += primes[i];              // running sum
      digest[3] += digest[2] * primes[i];  // Hornerish sum
   }

ei zwei (nicht abhängigen) Muls pro Primzahl ist die Geschwindigkeit angemessen genug, und bis auf die einfache Summe hat jede der Komponenten immer alle Fehler aufgedeckt, die ich versucht habe, mich an der Zusammenfassung vorbei zu schleichen. Ich bin jedoch kein Mathematiker, und empirische Tests sind keine Garantie für die Wirksamkeit.

Gibt es einige mathematische Eigenschaften, die ausgenutzt werden können, um eine vernünftige, zuverlässige Prüfsumme zu entwerfen - anstatt wie ich zu "kochen"?

Ist es möglich, die Prüfsumme so zu gestalten, dass sie schrittweise ausgeführt werden kann, indem Teilbereiche separat verarbeitet werden und dann die Ergebnisse mit ein wenig Arithmetik kombiniert werden, um dasselbe Ergebnis zu erzielen, als wäre der gesamte Bereich in einer Prüfsumme zusammengefasst worden gehen? Das Gleiche wie es heutzutage bei allen fortgeschrittenen CRC-Implementierungen der Fall ist, um eine parallele Verarbeitung zu ermöglichen.

BEARBEITE Die Begründung für das aktuelle Schema lautet: Die Anzahl, die Summe und das Produkt hängen nicht von der Reihenfolge ab, in der Primzahlen zum Digest hinzugefügt werden. Sie können in separaten Blöcken berechnet und dann kombiniert werden. Die Prüfsumme ist abhängig von der Bestellung; Das ist seine Daseinsberechtigung. Es wäre jedoch schön, wenn die beiden Prüfsummen von zwei aufeinanderfolgenden Blöcken irgendwie kombiniert werden könnten, um die Prüfsumme des kombinierten Blocks zu ergeben.

Die Anzahl und die Summe können manchmal mit externen Quellen verglichen werden, z. B. mit bestimmten Sequenzen auf oeis.org, oder gegen Quellen wie die Chargen von 10 Millionen Primzahlen bei primos.mat.br (der Index gibt die erste und letzte Primzahl an, die Zahl == 10 Millionen ist impliziert). Kein Glück für Produkt und Prüfsumme.

Bevor ich viel Zeit und Rechenleistung in die Berechnung und Überprüfung von Digests stecke, die den gesamten Bereich kleiner Faktoren bis zu 2 ^ 64 abdecken. Ich würde gerne hören, was die Experten darüber denken ...

Das Schema, das ich derzeit in 32-Bit- und 64-Bit-Varianten teste, sieht folgendermaßen aus:

template<typename word_t>
struct digest_t
{
   word_t count;
   word_t sum;
   word_t product;
   word_t checksum;

   // ...

   void add_prime (word_t n)
   {
      count    += 1;
      sum      += n;
      product  *= n;
      checksum += n * sum + product;
   }
};

Dies hat den Vorteil, dass die 32-Bit-Digest-Komponenten den unteren Hälften der entsprechenden 64-Bit-Werte entsprechen. Das bedeutet, dass nur 64-Bit-Digests berechnet werden müssen, auch wenn eine schnelle 32-Bit-Überprüfung gewünscht wird. Eine 32-Bit-Version des Digests finden Sie in diesem einfachensieve Testprogramm @ Pastebin, zum Experimentieren. Der vollständige Monty in einer überarbeiteten Version mit Vorlagen ist in einer neueren Paste für @ enthalte ein Sieb, das bis zu 2 ^ 64-1 @ funktionie.