Dann wird oft beim "Timing" geschummelt: statt die Gesamtberechnungszeit, wird die Zeit eines Befehls angegeben, der sein Zwischenergebnis oft in Hexadezimalform vorliegen hat.
Ich halte nun folgende Testbedingungen für geeigneter:
- Argument n = 10^9 = 1 Mrd. (muss einstellbar sein, um Schummelabkürzungen zu entlarven)
- RAM-Disk {da Speicherzeit der über 200 MB unter 1 s}
- Messung der Gesamtzeit muss auch per Stoppuhr möglich sein
- das Ergebnis muss bis auf die letzte Stelle stimmen (Dateivergleich)
Hier nun die Ergebnisse bei 1 Thread-Berechnungen:
Zeiten für Fibonacci(10^9) {Intel i9 1 Kern /Single Thread}
Fibonacci(1Mrd): RAM-Disk Ges. (Schummel-Timing)
----------------------------------------------------------------------
YMP Takahashi 20 Threads 3.03 s 0.72 s Beitrag 8
YMP ln2 Haswell 20 Threads 3.74 s 1.38 s Beitrag 7
YMP ln2 Haswell 9.31 s 6.98 s Beitrag 3
gmp 6.2 gmpz_fib_ui 53.25 s 5.28 s
Pari GP 2.9.1 70.7 s 10.08 s
Mathematica 11.3:
- Fibonacci[1000000000] 56.64 s 5.14 s
- MatrixPower[{{1,1},{1,0}},n].. 70.57 s (trotz 2 Threads langsamer)
- [(GoldenRatio^(10^9))/Sqrt[5]] 249.37 s 191.67 s
Round[HypergeometricPFQ[...] über 4 min -
JAVA ln2 optimiert 33.7 min -
Hat jemand noch andere Sprachen, eigene Programme, interessante Algorithmen oder LINKs ?
3 hypergeometrische Funktionen habe ich getestet -> jedoch alle zu langsam.
Noch schneller könnte man mit dem ymp-Code des Pi-Weltmeisters werden...
Gesucht ist auch nicht die schnellste CPU (ich kann gern meine gmpz_fib_ui.exe zur Verfügung stellen), sondern der schnellste Algorithmus: mathematisch & Maschinen-Code-technisch.
hyperG
Senior Dabei seit: 03.02.2017 Mitteilungen: 1424
Beitrag No.3, vom Themenstarter, eingetragen 2021-02-28
So, YMP (NumberFactory vom Pi-Weltmeister) habe ich tatsächlich zum Laufen bekommen!
UNGLAUBLICH was der Alexander J. Yee da für ein hochoptimiertes Grundgerüst geschaffen hat!
Der JAVA Algorithmus, der mit O(log2) nur 29 Iterationen benötigt,
braucht mit YMP für die 208.987.640stellige Zahl sage und schreibe nur 9.3 s
-> 5.73 mal schneller als GMP!!!
Das Bild zeigt schön die Teilschritte:
i9 mit Hashwell Befehlssatz
Timing (hex Berechnung): 6.9 s (1 Thread)
Konvertierung in Dezimal 2.2 s (20 Threads)
Schreiben RAM-Disk 0.1 s
Gesamtzeit: 9.3 s
Mit dem älteren Befehlssatz SandyBridge (z.B. i7)
14.5 s -> immer noch 3.7 mal schneller als GMP.
hyperG
Senior Dabei seit: 03.02.2017 Mitteilungen: 1424
Beitrag No.6, vom Themenstarter, eingetragen 2021-02-28
Oh, danke endy! Ihr hattet ja bereits 2013 dieses Thema.
Ich habe Mathematica V 11.3 & 12. Da wurde vermutlich genau Dein genannter Algorithmus verwendet, denn Timing zeigt fast identische Werte:
Timing[Fibonacci[1000000000];] -> 5.140625 s
Timing[Fibtakahashi[1000000000];] -> 5.171875 s
ABER wie bereits gesagt, zeigt Timing nur die Zeit bis zur Berechnung des internen Zwischenergebnisses an! Um diese aus den Kern heraus zu bekommen, dauert es dann noch mindestens 51 s. Die 0.1 s Speicherzeit in die schnelle RAM-Disk sind zu vernachlässigen.
Zwar zeigt Fibtakahashi nur minimale Unterschiede, aber ich werde ihn mal mit YMP testen.
Die Parallelisierung scheint mit dem im Beitrag 1 beschriebenen Algo. besser realisierbar, da die beiden Quadrierungen unabhängig erledigt werden könnten.
hyperG
Senior Dabei seit: 03.02.2017 Mitteilungen: 1424
Beitrag No.9, vom Themenstarter, eingetragen 2021-03-02
Hallo endy,
Ich habe zwar immer noch kein Internet, aber ich wollte mich noch für den gut aufbereiteten Code bedanken. Er sieht zunächst umständlicher aus, aber 1 Iteration weniger macht bei 1 Mrd Stellen viel aus. Ausserdem hat man damit eine gute Validierung. Ab 4,3 Mrd. reichen 32 Bit Variablen (Maske) nicht mehr.
Ich kann nun 1 Mrd Fibonacci-Stellen doppelt so schnell berechnen wie 1 Mrd. Pi Stellen :-)
Grüße Gerd
hyperG
Senior Dabei seit: 03.02.2017 Mitteilungen: 1424
Beitrag No.11, vom Themenstarter, eingetragen 2021-03-03
Hallo endy,
was auch noch toll ist: der Takahashi-Algorithmus beinhaltet ja
auch Lucas Zahlen -> es reichen kleine Änderungen und schon hat man auch diese Funktion. Die Geschwindigkeit liegt zwischen den beiden anderen:
Benchmark Lucas(10^9) & Lucas(10^10)
10^9 : 3.38 s (Timing 1 s)
10^10: 42.31 s (Timing 12 s)
hyperG
Senior Dabei seit: 03.02.2017 Mitteilungen: 1424
Beitrag No.12, vom Themenstarter, eingetragen 2021-03-03
Beim Vergleich mit Mathematica könnte man bei Geschwindigkeitsverbesserung von Faktor 18 zunächst an die 20 Threads denken.
ABER spätestens ab 10^10 und Faktoren über 21 wird klar, dass der Weltmeister hier mit hoch optimierten Maschinencode (FFT-Multiplikation, AVX2,...) arbeitet. Von YMP zu y-cruncher gibt es dann nochmals Verbesserungen (AVX512,..), aber die sind nicht zugänglich.
mit größer werdenden Argumenten wächst der Vorsprung weiter
Fibinacci(500 Mio):
FibTakahashi: 1.492 s (Timing 0.37 s)
Mathema V12: 25.39 s (Timing 2.39 s) 17.01742627 mal langsamer
1 Mrd:
FibTakahashi: 3.03 s (Timing 0.73 s)
Mathema V12: 56.64 s (Timing 5.14 s) 18.6930693 mal langsamer
10 Mrd:
FibTakahashi: 38.3 s
Mathema V12 : 824.916061 s 21.538 mal langsamer
hyperG
Senior Dabei seit: 03.02.2017 Mitteilungen: 1424
Beitrag No.14, vom Themenstarter, eingetragen 2021-03-03
Ja pzktupel,
mit dieser neuen YMP-Bib. wird selbst pfgw wieder interessant,
da:
GMP zwar minimal langsamer als pfgw64,
aber ymp viel schneller als GMP ist!
Besonders bei sehr großen Zahlen könnte ein schneller Vorfilter für mögliche Primzahlen
interessant werden.
Zu beachten ist jedoch, dass 1 exe bereits alle Kerne an sich reißt & man bei Multitasking nicht mehr mehrere EXE starten darf.
Das kann man aber bei Bedarf abschalten.
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Themenstart: 2021-02-27
Notiz
Profil
Quote
Link
