„Prime95“ – Versionsunterschied
[gesichtete Version] | [gesichtete Version] |
K →Faktorisierungsmethoden und Primzahltest: probedivision aktualisiert |
|||
Zeile 231: | Zeile 231: | ||
Die ersten beiden Faktorisierungsmethoden werden dem eigentlichen [[Primzahltest]], dem sogenannten [[Lucas-Lehmer-Test]], vorgeschaltet, um vergleichsweise kleine Faktoren zu finden und somit den rechenaufwendigen Primzahltest zu vermeiden. Sollte dieser Test ergeben, dass die Zahl zusammengesetzt ist, kann mit der ECM-Methode weiter nach Faktoren mit einer Länge bis etwa 60 Stellen gesucht werden. Hiernach wird zum [[Zahlkörpersieb]] übergegangen, das vom [[BOINC]]-Projekt ''NFS@Home'' angeboten wird. |
Die ersten beiden Faktorisierungsmethoden werden dem eigentlichen [[Primzahltest]], dem sogenannten [[Lucas-Lehmer-Test]], vorgeschaltet, um vergleichsweise kleine Faktoren zu finden und somit den rechenaufwendigen Primzahltest zu vermeiden. Sollte dieser Test ergeben, dass die Zahl zusammengesetzt ist, kann mit der ECM-Methode weiter nach Faktoren mit einer Länge bis etwa 60 Stellen gesucht werden. Hiernach wird zum [[Zahlkörpersieb]] übergegangen, das vom [[BOINC]]-Projekt ''NFS@Home'' angeboten wird. |
||
Im Normalfall erfolgt die Zuweisung von zu testenden Zahlen automatisch durch PrimeNet. Die Grenze, bis zu der Faktoren im Rahmen der der Probedivision gesucht werden, ist abhängig von der zu testenden Zahl und steigt mit ihrer Größe an |
Im Normalfall erfolgt die Zuweisung von zu testenden Zahlen automatisch durch PrimeNet. Die Grenze, bis zu der Faktoren im Rahmen der der Probedivision gesucht werden, ist abhängig von der zu testenden Zahl und steigt mit ihrer Größe an. Die aufwandsoptimalen Obergrenzen sind in der Tabelle ''Probedivision'' genannt. Durch den derzeitigen Überschuss an Berechnungskapazitäten im Bereich Probedivision - insbesondere auf Grund der GPU-Untersützung mittels ''mfaktc'' - werden seit August 2011 höhere Obergrenzen verwendet.<ref name="GIMPS_MF_Post">MersenneForum.org: Factoring bit depth? [http://www.mersenneforum.org/showthread.php?p=268541#post268541]</ref> Da der Aufwand der Probedivision nur von der Größe des Faktors abhängt, ist das Verfahren durch die Verdopplung der Testintervalle für größere Faktoren ungeeignet. Es benötigt im Vergleich zu den beiden anderen Verfahren jedoch kaum Arbeitsspeicher. |
||
Das P-1-Verfahren erfolgt im Anschluss an die Probedivision und findet mittelgroße Faktoren, die stark zusammengesetzt sind. Man weiß, dass mögliche Faktoren q von <math>2^p-1</math> den Aufbau <math>q=2*k*p+1</math> haben müssen.<ref name="GIMPS_Math">GIMPS: ''The Math'' [http://www.mersenne.org/various/math.php]</ref> Der Teil k ist hierbei meist selbst zusammengesetzt. Das Verfahren findet den Faktor q, solange alle Faktoren von k kleiner als die sogenannte B1-Grenze sind (Stufe 1) oder alle bis auf einen kleiner als B1 und der verbleibende letzte Teilfaktor von k kleiner als die sogenannte B2-Grenze ist (Stufe 2, mit B2≈30*B1). In seltenen Fällen können durch die sogenannte [[Brent-Suyama Erweiterung]] aber auch Faktoren gefunden werden, die das B2-Kriterium eigentlich nicht erfüllen.<ref name="Brent-Suyama">MersenneForum.net: [http://www.mersenneforum.org/showpost.php?p=268005&postcount=193]</ref> Der Berechnungsaufwand ist abhängig von der Größe des Exponenten sowie der Wahl von B1 und B2. Stufe 2 benötigt viel Arbeitsspeicher. |
Das P-1-Verfahren erfolgt im Anschluss an die Probedivision und findet mittelgroße Faktoren, die stark zusammengesetzt sind. Man weiß, dass mögliche Faktoren q von <math>2^p-1</math> den Aufbau <math>q=2*k*p+1</math> haben müssen.<ref name="GIMPS_Math">GIMPS: ''The Math'' [http://www.mersenne.org/various/math.php]</ref> Der Teil k ist hierbei meist selbst zusammengesetzt. Das Verfahren findet den Faktor q, solange alle Faktoren von k kleiner als die sogenannte B1-Grenze sind (Stufe 1) oder alle bis auf einen kleiner als B1 und der verbleibende letzte Teilfaktor von k kleiner als die sogenannte B2-Grenze ist (Stufe 2, mit B2≈30*B1). In seltenen Fällen können durch die sogenannte [[Brent-Suyama Erweiterung]] aber auch Faktoren gefunden werden, die das B2-Kriterium eigentlich nicht erfüllen.<ref name="Brent-Suyama">MersenneForum.net: [http://www.mersenneforum.org/showpost.php?p=268005&postcount=193]</ref> Der Berechnungsaufwand ist abhängig von der Größe des Exponenten sowie der Wahl von B1 und B2. Stufe 2 benötigt viel Arbeitsspeicher. |
Version vom 11. August 2011, 19:40 Uhr
Prime95/MPrime
| |
---|---|
![]() | |
Prime95 bei der Probedivision | |
Basisdaten
| |
Entwickler | George Woltman |
Aktuelle Version | 26.6 (9. April 2011) |
Betriebssystem | Windows (Prime95), Mac OS X (Prime95), Linux (MPrime), FreeBSD |
Programmiersprache | C, ASM86 |
Kategorie | Primzahltester, besonders für Mersenne-Primzahlen; Benchmark |
Lizenz | Freeware, aber Kopplung an PrimeNet falls Suche nach Mersenne-Primzahlen |
deutschsprachig | nein |
http://www.mersenne.org/ |
Prime95 [[1] (prime95.exe) ist ein Programm für Windows und Mac OS X zum Testen der Primalität einer Mersenne-Zahl mit Hilfe des sogenannten Lucas-Lehmer-Tests. Es wird von GIMPS, der großen Internet Mersenne-Primzahl Suche, angeboten und von George Woltman als Software für Verteiltes Rechnen (distributed computing) entwickelt. Die Softwareversionen für GNU/Linux und FreeBSD werden MPrime [ ][1] genannt.
]Die neun größten bekannten Primzahlen wurden mit Hilfe von Prime95 gefunden[2]. Rekordhalter ist die am 23. August 2008 gefundene und mit 100.000 US-Dollar von der Electronic Frontier Foundation prämierte erste bekannte Primzahl mit mehr als 10 Millionen Stellen: . Ein Teil dieser Prämie wird an die Teilnehmer ausgeschüttet.[3]
Das Programm verfügt über eine der schnellsten bekannten Implementierungen für Multiplikationen, in dem es hochoptimierten Prozessor-Code zur Durchführung von schnellen Fourier-Transformationen verwendet. Die zugehörigen Routinen stehen als gwnum-Bibliothek zur Verfügung und werden von einigen anderen Programmen eingesetzt. Die Bibliothek ist frei nutzbar, jedoch müssen bei der Suche nach Mersenne-Primzahlen die Projektbedingungen eingehalten werden.[4]
Einsatzzwecke
Verteiltes Rechnen
Das Programm kann als Software-Client für das verteilte Rechnen (distributed computing) mit PrimeNet, einer von GIMPS betriebenen zentralen Datenbank für Mersenne-Primzahlen, betrieben werden. Es verbindet sich dann in regelmäßigen Abständen mit dem GIMPS PrimeNet-Server, um neue Arbeit anzufordern und fertige Ergebnisse abzuliefern. Die Berechnung erfolgt auf der CPU, während diese ungenutzt ist. Eine offizielle Unterstützung für GPUs existiert noch nicht. Mit CUDALucas (Lucas-Lehmer-Test) und mfaktc (Probedivision) existieren allerdings zwei CUDA-fähige Programme, deren Ergebnisse vom Server ebenfalls akzeptiert werden. Das PrimeNet verfügt Mitte 2011 über rund 62 Teraflops Rechenleistung[5].
Stresstest
Von PC Enthusiasten wird Prime95 gerne beim CPU Overclocking als Stabilitätstest eingesetzt, da das Programm die CPU relativ stark[6] auslastet, woraus eine starke Wärmebelastung resultiert, die oft den kritischen Faktor darstellt. Programminterne Plausibilitätsprüfungen der Rechenergebnisse liefern eine Qualitätskontrolle, die hardwarebedingte Rechenfehler des übertakteten Computersystems offenbaren.
Rechenleistung
Das Programm kann als Benchmark verwendet werden. Die Ergebnisse können der Öffentlichkeit automatisch zum Vergleich dargestellt werden.
Vergleich der CPU-Rechenleistungt m. H. des Prime95 und MPrime v26.6 Benchmarks[7][8] | |||||||||
---|---|---|---|---|---|---|---|---|---|
Platform/CPU-Modell | Frequenz (pro Kern) in MHz |
Kerne | Prime95 FFT (mit 2048k-Länge) in ms |
Prime95 FFT (mit 4096k-Länge) in ms |
Prime95 Probedivision (65 Bit Faktorlänge) in ms |
TDP in Watt | rel. Durchsatz[9] pro Kern & Tag[10] | Durchsatz[9] pro Kern & Tag bei 1GHz[10] | Durchsatz[9] pro Watt & Kern & Tag bei 1GHz[10][11] |
Intel Atom D510 | 1664 | 2 | 585,91 | 1954,40 | 25,65 | 13[12] | 0,23 | 0,14 | 0,0215 |
AMD Fusion E-350 | 1596 | 2 | 222,03 | 491,02 | 15,18 | 18[13] | 0,40[14] | 0,25 | 0,0278 |
Intel Pentium III | 1151 | 1 | 438,10 | 922,58 | 50,59 | 30[15] | 0,31 | 0,27 | 0,0090 |
AMD Athlon | 1054 | 1 | 457,40 | 774,49 | 56,08 | 60[16] | 0,36 | 0,34 | 0,0057 |
AMD Athlon XP 2000+ | 1640 | 1 | 201,21 | 448,28 | 32,80 | 70[17] | 0,41 | 0,25 | 0,0036 |
Intel Pentium 4 | 3078 | 1 | 72,40 | 162,02 | 14,91 | 82[18] | 1,50 | 0,49 | 0,0060 |
AMD Phenom II X4 | 3414 | 4 | 34,86 | 76,27 | 4,59 | 125[19] | 4,32 | 1,27 | 0,0406 |
Intel Core2 Duo E8600 | 3334 | 2 | 34,15 | 73,07 | 4,89 | 65[20] | 4,17 | 1,25 | 0,0385 |
Sandy Bridge Pentium G620T | 2159 | 2 | 41,09 | 72,53 | 4,99 | 35[21] | 3,54 | 1,64 | 0,0937 |
AMD Phenom II X6 1100T | 3310 | 6 | 32,68 | 69,54 | 3,85 | 125[22] | 4,03 | 1,22 | 0,0586 |
Intel Core i5-2500K | 3330 | 4 | 23,94 | 53,24 | 3,49 | 95[23] | 5,90 | 1,77 | 0,0745 |
Intel Core i7-2600K | 3463 | 4 | 21,75 | 45,35 | 3,67 | 95[24] | 6,17 | 1,78 | 0,0749 |
Faktorisierungsmethoden und Primzahltest
Prime95 kann zur Faktorisierung von Zahlen der Form benutzt werden. Im Normalfall sucht es jedoch nur nach Mersenne-Primzahlen, für die a=1, b=2 und d=-1 gilt, mit Exponent c prim.
Das Programm unterstützt drei Faktorisierungsmethoden:
Exponent bis zu | Obergrenze |
---|---|
3.960.000 | 260 |
5.160.000 | 261 |
6.515.000 | 262 |
8.250.000 | 263 |
13.380.000 | 264 |
23.390.000 | 265 |
29.690.000 | 266 |
38.300.000 | 267 |
48.800.000 | 268 |
60.940.000 | 269 |
77.910.000 | 270 |
96.830.000 | 271 |
120.000.000 | 272 |
153.400.000 | 273 |
199.500.000 | 274 |
253.500.000 | 275 |
322.100.000 | 276 |
408.400.000 | 277 |
516.800.000 | 278 |
Die ersten beiden Faktorisierungsmethoden werden dem eigentlichen Primzahltest, dem sogenannten Lucas-Lehmer-Test, vorgeschaltet, um vergleichsweise kleine Faktoren zu finden und somit den rechenaufwendigen Primzahltest zu vermeiden. Sollte dieser Test ergeben, dass die Zahl zusammengesetzt ist, kann mit der ECM-Methode weiter nach Faktoren mit einer Länge bis etwa 60 Stellen gesucht werden. Hiernach wird zum Zahlkörpersieb übergegangen, das vom BOINC-Projekt NFS@Home angeboten wird.
Im Normalfall erfolgt die Zuweisung von zu testenden Zahlen automatisch durch PrimeNet. Die Grenze, bis zu der Faktoren im Rahmen der der Probedivision gesucht werden, ist abhängig von der zu testenden Zahl und steigt mit ihrer Größe an. Die aufwandsoptimalen Obergrenzen sind in der Tabelle Probedivision genannt. Durch den derzeitigen Überschuss an Berechnungskapazitäten im Bereich Probedivision - insbesondere auf Grund der GPU-Untersützung mittels mfaktc - werden seit August 2011 höhere Obergrenzen verwendet.[26] Da der Aufwand der Probedivision nur von der Größe des Faktors abhängt, ist das Verfahren durch die Verdopplung der Testintervalle für größere Faktoren ungeeignet. Es benötigt im Vergleich zu den beiden anderen Verfahren jedoch kaum Arbeitsspeicher.
Das P-1-Verfahren erfolgt im Anschluss an die Probedivision und findet mittelgroße Faktoren, die stark zusammengesetzt sind. Man weiß, dass mögliche Faktoren q von den Aufbau haben müssen.[27] Der Teil k ist hierbei meist selbst zusammengesetzt. Das Verfahren findet den Faktor q, solange alle Faktoren von k kleiner als die sogenannte B1-Grenze sind (Stufe 1) oder alle bis auf einen kleiner als B1 und der verbleibende letzte Teilfaktor von k kleiner als die sogenannte B2-Grenze ist (Stufe 2, mit B2≈30*B1). In seltenen Fällen können durch die sogenannte Brent-Suyama Erweiterung aber auch Faktoren gefunden werden, die das B2-Kriterium eigentlich nicht erfüllen.[28] Der Berechnungsaufwand ist abhängig von der Größe des Exponenten sowie der Wahl von B1 und B2. Stufe 2 benötigt viel Arbeitsspeicher.
Die ECM erfolgt nach dem Lucas-Lehmer-Test und findet große Faktoren. Die Exponenten aus der automatischen ECM-Zuweisung sind derzeit siebenstellig. Eine Zuweisung erfolgt nur nach entsprechender Einstellung in Prime95 oder manueller Anforderung über die Projekt-Webseite. Es verfügt ebenfalls über eine B1- und B2-Grenze (B2=100*B1). Auch hier benötigt Stufe 2 viel Arbeitsspeicher.
Programmoptionen
Abkürzung | Bedeutung |
---|---|
GIMPS | was Sinn macht (Serverwahl, Standardeinstellung) |
TF | Probedivision |
TF-LMH | Probediv. LMH(Lone Mersenne Hunters), kleine Faktoren |
PM1-L | Faktorisierung P-1, große Expon. (vor Lucas-Lehmer) |
PM1-S | Faktorisierung P-1, kleine Exponenten (zukünftig) |
LL | LL (Lucas-Lehmer) Ersttest |
LL-WR | LL Test, Weltrekordgröße |
LL-10M | LL Test, mehr als 10 Millionen Stellen |
LL-100M | LL Test, mehr als 100 Millionen Stellen |
LL-NF | LL Test ohne vorherige Faktorisierung |
D | LL Zweittest |
ECM | Faktorisierung per ECM, kleine Exponenten |
ECM-F | Faktorisierung per ECM von Fermatzahlen |
Abkürzung | Bedeutung |
---|---|
F | faktorisiert durch Probedivision |
F-PM1 | faktorisiert durch P-1 |
F-ECM | faktorisiert durch ECM |
NF | kein Faktor durch Probedivision |
NF-PM1 | kein Faktor durch P-1 |
NF-ECM | kein Faktor durch ECM |
C | LL Test zusammengesetzt |
P | LL Test prim |
Auf der Projekt-Webseite kann in den Worker Windows (Prime95) bzw. Workers (MPrime) festgelegt werden, welche Art von Arbeit man erhalten möchte, zum Beispiel ein Faktorisierungsverfahren oder den Lucas-Lehmer-Test. Dies kann auch im Programm selbst vergenommen werden. Unter Status sieht man die Arbeiten, die man erhalten hat, sowie die erwarteten Vervollständigungsdaten. Die Arbeiten werden in der Datei worktodo.txt gespeichert. Bei Unreserve Exponent kann man einen Exponenten freigeben. Die Prozentzahl einer erledigten Arbeit wird automatisch an GIMPS weitergeleitet, man kann sie jedoch auch im Programm bei Manual PrimeNet Communication (Advanced → Manual Communication...) manuell zur Website schicken, indem man ein Häkchen bei Send new expected completion dates to server setzt. Dabei werden die neuen Vervollständigungsdaten zum Server geschickt.
Man kann mit dem Programm anonym oder mit einem GIMPS-Account arbeiten. Der Account sowie der Computername muss im Fenster Configure PrimeNet (Test → PrimeNet...) eingegeben werden. Will man anonym arbeiten, muss man die Felder leer lassen. Die Ergebnisse sind in der Datei results.txt ersichtlich, die Erneuerungen in Versionen in der Datei whatsnew.txt.
Versionen
![](https://upload.wikimedia.org/wikipedia/commons/thumb/7/7a/Prime95_v26_3.png/220px-Prime95_v26_3.png)
- Version 26 (Stabil), letzte Version 26.6, 4. April 2011 (~20% Beschleunigung für Core-iX-Generation im Vergleich zu Version 25; noch keine 'Intel AVX' Unterstützung)
- Version 25, letzte Version 25.11, 13. Juli 2009 (PrimeNet 5.0 Protokoll)
- Version 24, letzte Version 24.14, Februar 2006 (PrimeNet 4.0 Protokoll)
Referenzen
- ↑ a b Oxford Advanced Learner's Dictionary: prime, ninety, five und M
- ↑ The "Top Ten" Record Primes [1]
- ↑ GIMPS: Research Discovery Awards [2]
- ↑ GIMPS: Software End User License Agreement ("EULA") [3]
- ↑ GIMPS: PrimeNet Activity Summary PrimeNet Aggregate Computing Power 06-2011
- ↑ Christof Windeck: Hitzewelle, c't 15/2010 vom 5.7.2010, Seite 174ff
- ↑ Prime95 Benchmarks
- ↑ MPrime CPU Benchmarks und Durchsatz
- ↑ a b c FFT throughput, FFTsize 1024K, Avg Exp M20,950,000, siehe [4].
- ↑ a b c Gemessen in GHz-days per day per W, siehe GIMPS CPU Throughput calculator; leichte Abweichungen bei anderen FFT Faktorlängen, abweichende Leistungsbilder bei MPrime Probedivision. Referenzfehler: Ungültiges
<ref>
-Tag. Der Name „ghzdays“ wurde mehrere Male mit einem unterschiedlichen Inhalt definiert. - ↑ Die Werte verschlechtern sich bei übertackteten Maschinen exponentiell
- ↑ [5]
- ↑ [6]
- ↑ geschätzt
- ↑ [7]
- ↑ [8]
- ↑ [9]
- ↑ [10]
- ↑ [11]
- ↑ [12]
- ↑ [13]
- ↑ [14]
- ↑ [15]
- ↑ [16]
- ↑ [17]
- ↑ MersenneForum.org: Factoring bit depth? [18]
- ↑ GIMPS: The Math [19]
- ↑ MersenneForum.net: [20]
Siehe auch
Weblinks
- Download von Prime95
- FTP-Verzeichnis von GIMPS - enthält unterschiedliche Versionen von Prime95
- Benchmarks
- Forum
- NFS@Home