Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/03165.jsonl.gz/1588

Primzahlen
Ueber längere Zeit habe ich mich intensiv mit der Charakteristik von Primzahlen auseinandergesetzt.
Eine Herausforderung war dann auch eine grösste bekannte Primzahl zu suchen. Es gibt da ein Projekt mit namen GIMPS. An diesem Projekt sind Weltweit zehntausende Computer beteiligt. Fast zweieinhalb Jahre waren diese Computer nach der Suche einer grössten noch nicht bekannten Primzahl. Am 17.November 2003 war eine neue Primzahl gefunden worden. Es ist die vierzigste Mersenne’sche Primzahl. Die 20'996'011-te Zweierpotenz -1. Diese Zahl hat 6'320'430 Dezimalstellen. Die Zahl ist so gross dass man sie nicht einmal mit etwas veraunschaulichen könnte. Mit einer verhältnissmässig winzigen Zahl von 200 Dezimalstellen, kann man nämlich bereits jedes Atom im Universum nummerieren.
Eine Mersenn’sche Primzahl hat die Form (2 hoch n)-1 wobei n eine Primzahl sein muss.
Für mich war es natürlich nicht intressant, einer von den Zehntausenden Usern zu sein. Ich mache nämlich keine Glücksspiele. Vielmehr suchte ich nach einem neuen Algorithmus zur Bestimmung von Mersenne’schen Primzahlen oder um eine effizientere Lösung der Implementation des bisher schnellsten Algorithmen.
Ich hatte etliche Dinge untersucht, um einen neuen Algorithmus anwenden zu können. Zuguterletzt habe ich zwar einiges begriffen aber nach wie vor blieb der Lucas-Lehmer Test der effizienteste um Mersenne’sche Primzahlen zu testen.
Also gut, ich implementierte zuerst einmal den Lucas-Lehmer Test für kleine Zahlen. Dann baute ich einen Rechner mit den Grunrechenoperationen für riesige Zahlen mit Millionen von Dezimalstellen. Diesen Rechner verwendete ich dann für den Lucas-Lehmer Test.Den Rechner kannst Du dir übrigens Gratis herunterladen mit folgendem Link: Riesiger Rechner
Dieser Rechner basierte auf Schulmathematik und war natürlich viiiiel zu langsam. Aber ich brauchte unbedingt diese Implementation um andere Verfahren überprüfen zu können.
Für den Lucas-Lehmer Test brauchte ich folgende Funktionen:
A eine Funktion um eine Zahl zu Quadrieren.
B eine Funktion um von einer Zahl 2 zu subtrahieren. (jaja, tönt simpl ….)
C eine Funktion um den Rest einer Divison, mit der Mersenne’schen Zahl als Divisor, zu bestimmen. (Modulofunktion)
B Die Funktion um -2 zu subtrahieren, kann effizient programmiert werden unter Berücksichtigung, dass sie nur in extrem ungünstigen Fällen, welche extrem selten auftreten, einige tausendstel Sekunen CPU Zeit verbraucht.
C Eine superelegante Lösung habe ich für die Restwertdivision gefunden. Die Lösung ist einfach und trotzdem hammer gut. Wie es geht ist kein Geheimnis, wenns Dich intressiert dann klicke auf folgenden Link: Pitri's Restwertberechnung
A Es bleibt noch einen effizienten Algorithmus zum Quadrieren zu finden.
Das ist wirklich ein happiges Problem und hat mich lange beschäftigt. Nachdem ich einige effizientere Multiplikationsalgorithmen, als den Algorithmus der Schulmathematik, studiert habe, musste ich einsehen, dass auch mit den besseren nicht das gelbe vom Ei erreicht wird.
Nach ‚Schönhage und Strassen’ lässt sich mittels (missbrauchen) der ‚Fourier-Transformation’ eine sehr schnelle Multiplikation durchführen. Von der Fourier Transformation hatte ich keinen Schimmer…. Wie war das schon wieder mit den komplexen Zahlen… zum Glück habe ich gute Freunde welche mir da wieder mal einiges erklärt haben. Und siehe da, die Fourier Transformation ist ja gar nicht schwierig durchzuführen. Aber was schwierig ist, das ist die Fourier Transformation zu verstehen. Nun gut, als nächstes habe ich dann die Multiplikationsfunktion mit der Fourier Transformation implementiert und in den Lucas-Lehmer Test eingebaut. Das funktioniert wunderbar, aber ist viiiiiiel zu langsam. Wirklich effizientes Multiplizieren ist nur mit der Fast-Fourier-Multiplikation möglich. Nachdem ich mir auch diese zu Gemüte geführt habe, implementierte ich den Lucas-Lehmer Test auch noch mit der Fast-Fourier-Transformation. Endlich funktionierte die Sache recht effizient. Aber bei allem Respekt.. es war immer noch zu langsam….
Ich hatte während ich die Fast-Fourier-Transformation (abgek. FFT) studiert hatte, eine Frage welche ich niergends nachlesen konnte. Wieso rechnet man nicht mit einer möglichst grossen Basis ?
Würde man nämlich die FFT in einem anderen Zahlensystem rechnen so könnte man viel, sehr viel effizienter multiplizieren. Das heisst der Trick basiert eigentlich darauf, dass je grösser die Basis ist, je kleiner wird die Anzahl Koeffizienten für die Diskrete Fourier Transformation (abegk. DFT, Teil der FFT).
Ausgerichtet für mein Computer mit 32bit Archidektur wählte ich. statt das uns geläufige Zehnersytem, das Zahlensystem mit Basis 4294967296.
Das bringt natürlich sehr hohe Geschwindigkeitszunahme. Ein Inputvektor welcher zuvor im Dezimalsystem 20 Koeffizienten hatte braucht noch 3 Koeffizienten.
Ich habe also den ganzen Lucas-Lehmer Test umgeschrieben zur Basis
4294967296.
Das Funktionierte tatsächlich. Jedoch bereits bei Multiplikationen mit etwas über 500 Stellen stimmte das Ergebnis der Multiplikation nicht mehr.
Alle Programme habe ich in C geschrieben. In C hat ein Datentyp Longint 32 Bit und ein Datentyp Double 80 Bit. Wenn ich den grösstmöglichen Longint quadriere gibt das eine 64 Bit Zahl. Ich hatte ohne Ueberprüfung angenommen dass dieses Resultat absolut genau in einen Double Typ eingetragen wird. Dem ist eben nicht so. Obschon der Double Typ genug gross wäre um das Resultat aufzunehmen wird das Resultat gerundet.
Es blieb mir nichts anderes übrig als eine kleinere Basis nämlich 16 Bit also Basis 65536 zu wählen damit ich noch korrekte Resultate erhalte. Das ist natürlich sehr schlecht und verlangsamt den Algorithmus um das X-Fache. Die Inputvektoren werden doppelt so lang und die 32 Bit Archidektur meines Computers wird nicht ausgenutzt.
Trotzdem habe ich den Lucas-Lehmer Test umgeschrieben zur Basis
65536.
Endlich konnte ich grosse Zahlen Testen. Aber wieder gabe es Probleme. Mersenne’sche Primzahlen grösser (2 hoch 19937)-1 wurden nicht mehr korrekt berechnet….
Ich vermute, die berechneten Einheitswurzeln sind zu ungenau und daraus entstehen bei sehr grossen Multiplikationen Fehler. Die Einheitswurzeln berechne ich mit Sinus und Cosinus der Standartlibraries. Ich weiss also nicht wie genaue Resultate diese Funktionen liefern…..
Man muss sich schon im Klaren sein, ein einziges falsches Bit und alles ist im Eimer…..
Vielleicht untersuch ich das irgenwann.. aber für mich ist die Sache vorerst mal abgeschlossen. Ich habe einfach keine Zeit mehr um gratis an solchen Projekten zu arbeiten.
Warum habe ich überhaubt so viel Zeit investiert… Ich habe gehofft einen schnelleren Lucas-Lehmer Test zu programmieren als der bisherige von GIMPS. Leider bin ich steckengeblieben… obschon ich noch weitere Ideen zur Verbesserung hätte finde ich die Entscheidung richig, an diesem Punkt aufzuhören.
Falls sich jemand intressiet, kann er sich hier einige C-Sourcen und Exe Files downloaden.
Die C-Sourcen stelle ich zur freien Verfügung. Jede Source ist eine abgeschlossene Applikation. Es braucht keine speziellen Libraries. Compiliert werden kann jede C-Source als Konsolenapplikatione mit Visual C++ 6.0 . Ansonsten sind die enthaltenen Funktionen auch problemlos portierbar. Zur Downloadseite