Eine derartige Geschwindigkeit(sverbesserung) kann nur
durch vollständiges Ausnutzen aller Möglichkeiten eines Prozessors
erreicht werden, so daß wir unsere diesbezüglichen Programme
in Assemblersprache (Maschinensprache) verfaßten. Ein weiteres Beispiel
macht dies deutlich: Beim Quadrieren einer 500000-bit Zahl benötigt
das Berechnen des 1000000-bit Quadrates 0.305 Sekunden auf einer 40 MHz
SUN SS10 Workstation. Das entsprechende, in der Programmiersprache C
geschriebene Programm ist etwa dreimal langsamer. (Für die Schönhage-Strassen-Methode
ist die C-Version sogar zwölfmal langsamer.)
Erste Erfolge - Weltrekorde in der Computational Number Theory
Kehren wir zurück zur eingangs erwähnten Rekordjagd nach großen
Primzahlzwillingen. Salopp gesprochen lief die Suche wie folgt ab: Nach
einer einfachen Formel bestimmten wir gut hundert Millionen Zahlenpaare,
unter denen nach einer ähnlich wie oben formulierten Heuristik etwa
2 Primzahlzwillinge vermutet werden konnten. Ließ sich eine dieser
Zahlen durch einen Faktor kleiner als 1,4 Billionen teilen, so wurde das
betreffende Paar aus dem Rennen gezogen. |
Knapp 600000 potentielle Primzahlzwillinge überstanden
diese Prüfung. Sie wurden der Reihe nach dem probablistischen Test
unterzogen. Wir hatten bereits beim 55440. Kandidaten Glück und fanden
den erhofften Rekordzwilling. Präziser läßt sich das Such-Prinzip
folgendermaßen beschreiben:
-
Die Suche wurde für die Zahlen in der arithmetischen Progression
(3+30·h)238880 ±
1
geplant. Hierbei war der Exponent 38880 fest, während sich
h zwischen 0 und 227 bewegte.
- Aus dieser Folge wurden alle Zahlen herausgesiebt, die einen Faktor zwischen
7 und 44000·225 besitzen. Genau 594.866
Kandidaten blieben übrig.
- Danach durchliefen die Kandidaten einen probabilistischen Primzahltest,
zuerst der +1 Fall, danach der -1 Fall, bis ein "wahrscheinlicher Primzahlzwilling"
gefunden wurde. Dies war bereits beim 55440. Kandidaten der Fall.
|