|
|
|
|
|
|
|
|
Geschwindigkeitsvergleich (Benchmark) von &
mit 10 Mio. großen Primzahlen |
Stand: 10.02.2019 |
|
|
|
|
|
|
|
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 |
Ryzen 5 1500X 3.5GHz |
Ryzen 5 1600 3.4GHz |
i9-7900X 3.3...4.2 GHz |
AMD A6-5400K |
|
c++GMP x64 V6b 20 Threads |
106,3 s |
|
|
79,2 s |
34,7...36,4 s (3) |
|
|
c++GMP x64 V6 20 Threads |
121,6 s |
|
105,4 s |
75 s |
37,3...49,6 s (3) |
|
|
c++GMP x64 V5 20 Threads |
150,5 s |
|
|
|
67,57 s |
|
|
c++GMP x64 V5 8 Threads |
2,44 min |
3,05 min |
|
|
|
|
|
GP/PARI x64 1 Thread |
8,18 min |
|
|
|
|
|
|
mathematica 11.3 4 Thread |
|
|
|
|
9,61 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 (?) |
|
|
|
|
|
Mathematica |
|
|
|
|
|
82,63 min |
|
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 |
Ryzen 5 1500X 3.5GHz |
Ryzen 5 1600 3.4GHz |
i9-7900X 3.3...4.2 GHz |
AMD Phenom II X6 3GHz |
|
c++GMP x64 V6b 20 Threads |
30,06 s |
|
|
25,5 s |
12,3...12,7 s (3) |
52,9 s |
|
c++GMP x64 V6 20 Threads |
34,29 s |
|
31,78 s |
24,2 s |
13,18..16,92 s (3) |
|
c++GMP x64 V5 20 Threads |
74 s |
|
- |
|
36 s |
|
c++GMP x64 V5 8 Threads |
1,2 min (1) |
1,6 min |
- |
|
51,62 s |
|
c++GMP x64 V5 1 Thread |
5,01 min |
|
Core2 T9300 2.50GHz |
|
|
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 |
Ryzen 5 1500X 3.5GHz |
Ryzen 5 1600 3.4GHz |
i9-7900X 3.3...4.2 GHz |
|
c++GMP x64 V5 8 Threads |
58,6 s |
73 s |
55,6 s |
|
|
GP/PARI x64 1 Thread |
129 s |
|
|
|
|
|
|
c++GMP x64 V5 1 Thread |
254,8 s |
388 s |
|
|
|
|
|
mathematica 11.3 4 Threads |
|
|
|
|
338,99 s=5,65 min |
|
|
mathematica 11.3 1 Thread |
|
|
|
|
1387,86 s=23,1 min |
|
|
JAVA x64 BigInt |
35,4 min |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Test 4: Abkürzung mit ggT & PowMod, da Miller Rabin-Test in diesem Bereich ohne Fehler (ohne GMP.dll) |
|
|
|
|
|
|
|
|
Sprache \ CPU: |
i7-3770K
3.50GHz |
AMD
FX-8320 3.5 GHz |
Ryzen 5 1500X 3.5GHz |
Ryzen 5 1600 3.4GHz |
i9-7900X 3.3...4.3 GHz |
AMD Phenom II X6 3GHz |
|
c++ 128MulModRe 20 Threads |
23,4 s |
? |
? s |
? s |
7.39...7.5 s (4) |
? |
|
c++ 128MulModRe 20 Threads |
23,80 s |
17,87 s |
18,5 s |
13,2 s |
8,3...11,15 s (3) |
47,5 s |
|
c++ 128MulModRe 8 Threads |
22,41 s |
16,49 s (0) |
18,39 s |
|
20...24,69 s (3) |
|
c++ 128MulMod 8 Threads |
23,47 s |
17,66 s (0) |
|
|
|
c++GMP x64 V5 8 Threads | 24,4 s |
32,6 s |
|
|
|
c++GMP x64 V5 1 Thread | 105,8 s |
158,2 s |
|
|
|
GP/PARI x64 1 Thread |
157,9 s |
|
|
|
|
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! |
| | | |
|
(3) zunächst mit Meltdown und Spectre Update KB4056892 4% langsamer; nach BIOS Optimierung 4,2 GHz (-2 -5) dann über 20% schneller! |
| | | |
|
(4) 16.11.2022: Neue GCD Optimierung mit tzcnt/builtin_ctz |
| | | |
|
Vergl. |
Software-Geschwindigkeitsvergleich 3^x &
Liste-mathematische-Rekorde |
|
|
|
|
|
|
|
|