Geschwindigkeitsvergleich (Benchmark) von & mit 10 Mio. großen Primzahlen Stand: 09.04.2017
zunächst 128-Bit-Zahl aus Primzahleigenschaften
gegeben : Prime(1000000000000000000000000)=58310039994836584070534263
Ergebnis: Prime(1000000000000000010000000)=58310039994836584663869571
Test 1: Befehl NextPrime(x) (bis 1000stellige Zahlen keine Fehler bekannt)
Sprache   \   CPU: i7-3770K 3.50GHz AMD FX-8320 3.5 GHz
c++GMP x64 V5 8 Threads 2,44 min 3,05 min
GP/PARI x64      1 Thread 8,18 min  
c++GMP x64 V5 10,1 min  
c++GMP x32 V5 18,2 min  
c++GMP x32 V4 31 min  
JAVA x64 64 min > 2h (?)
c# x64 - (nur  J# )  
Test 2: Abkürzung mit ggT & PowMod, da Miller-Rabin-Test in diesem Bereich ohne Fehler
bekannte Fehler: Pseudoprimzahlen
Sprache   \   CPU: i7-3770K 3.50GHz AMD FX-8320 3.5 GHz Core2 T9300 2.50GHz
c++GMP x64 V5 8 Threads 1,2 min (1) 1,6 min -
c++GMP x64 V5 1 Thread 5,01 min   -
GP/PARI x64      1 Thread 8,18 min   - (kein 64 Bit möglich)
c++GMP x32 V5 1 Thread 11,38 min   23,46 min
JAVA x64           1 Thread (2) 11,57 min   -
c++ x64 192MulModRe 1Thread 14,60 min   -
c++ x64 192Bit WhileDouble 18,3 min 34,4 min -
c++GMP x32 V4 18,77 min    
c# x64 33,39 min    
c++ x64 192Bit WhileINT 45,5 min 47,3 min -
  Weiter ab hier mit Optimierung "nur bis 64 Bit" (also 10 Mio. 20stellige Primzahlen < 2^64 - 99)
gegeben : Prime(306268030480171300)=13169525310647365859
Ergebnis: Prime(306268030490171300)=13169525311087574047
Test 3: zunächst wieder mit NextPrime-Befehl
Sprache   \   CPU: i7-3770K 3.50GHz AMD FX-8320 3.5 GHz
c++GMP x64 V5 8 Threads 58,6 s 73 s
GP/PARI x64      1 Thread 129 s  
c++GMP x64 V5 1 Thread 254,8 s 388 s
JAVA x64 BigInt 35,4 min  
Test 4: Abkürzung mit ggT & PowMod, da Miller Rabin-Test in diesem Bereich ohne Fehler
Sprache   \   CPU: i7-3770K 3.50GHz AMD FX-8320 3.5 GHz
c++ 128MulModRe 8 Threads 22,41 s 16,49 s (0)
c++ 128MulMod 8 Threads 23,47 s 17,66 s (0)
c++GMP x64 V5 8 Threads24,4 s 32,6 s
c++GMP x64 V5 1 Thread105,8 s 158,2 s
GP/PARI x64      1 Thread    
c++ 128MulMod  1 Thread 162,9 s  
c++GMP x32 V5    
JAVA x64 BigInt    
c++GMP x32 V4    
c# x64                 1 Thread 13,81 min 19,4 min
(0) Dieser letzte Test zeigt, dass gleichgetakete AMD-CPUs mit Ganzzahl 64Bit-MulMod schneller sind,
während Intel CPUs bei Floating Point & AVX-Befehlen schneller rechnen.
Die GMP Programme schaffen trotz 8 Threads nicht mal Verbesserungsfaktor 6, da die GMP-Befehle aus externer DLL die Parallelisierung ausbremsen.
(1) Mit 7 statt 8 Threads kaum messbare Verschlechterung. (vermutlich weil Turbo-Boost-Modus bei 89% etwas länger aktiv bleibt als bei 100% CPU-Last)
(2) JAVA schneidet nur deshalb so gut ab, weil PowMod per "Montgomery reduction" statt langsame while Schleife!
Vergl. Software-Geschwindigkeitsvergleich 3^x