Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Suche Fibonacci(10^9) Benchmarks
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Suche Fibonacci(10^9) Benchmarks
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1426
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-02-27


Hallo zusammen,

im Internet wimmelt es nur so von Anfänger-Programmen zur Berechnung (angeblich) großer Fibonacci Zahlen.
( discourse.julialang.org/t/recursive-fibonacci-benchmark-using-top-languages-on-github/15602
fib(46) in über 9 s

z.B. pybenchmarks.org/u64q/performance.php?test=fibonacci
mit nur n= 1 Mio. -> viele Zeiten unter 0.3 s
kaum objektiver Vergleich möglich { Speicherzeit bei Festplatten usw.}
)

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.

Grüße Gerd



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1426
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, vom Themenstarter, eingetragen 2021-02-28


Einen interessanten Algorithmus gibt es unter
codereview.stackexchange.com/questions/109429/computing-even-huger-fibonacci-numbers-in-java-follow-up
wo man mit JAVA Fibonacci(10^7) in weniger als 2 s berechnen kann.

Den habe ich mit 10^9 laufen lassen und 33,7 min benötigt.

Tabelle oben erweitert.

Hat jemand Python?
Python
def fibonacci(n):
    f_n, f_n_plus_1 = 0, 1
    for i in range(n.bit_length() - 1, -1, -1):
        f_n_squared = f_n * f_n
        f_n_plus_1_squared = f_n_plus_1 * f_n_plus_1
        f_2n = 2 * f_n * f_n_plus_1 - f_n_squared
        f_2n_plus_1 = f_n_squared + f_n_plus_1_squared
        if n >> i & 1:
            f_n, f_n_plus_1 = f_2n_plus_1, f_2n + f_2n_plus_1
        else:
            f_n, f_n_plus_1 = f_2n, f_2n_plus_1
    return f_n

Man muss bei 10^7 schon unter 2 s schaffen, damit ein Start von n=10^9 nicht länger als 33 min dauert.

Nachtrag: Algorithmus scheint von hier:
blog.richardkiss.com/?p=398



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haegar90
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.03.2019
Mitteilungen: 598
Herkunft: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2021-02-28


..war wohl off-topic.


-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1426
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.

Grüße Gerd



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1426
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2021-02-28


2021-02-28 12:42 - haegar90 in Beitrag No. 2 schreibt:
..war wohl off-topic.

Nanu, da stand doch gerade viel interessantes...
Interessiert mich auch, wie schnell F das kann.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
endy
Senior Letzter Besuch: im letzten Monat
Dabei seit: 10.01.2011
Mitteilungen: 3226
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2021-02-28


Hallo.

Siehe Klick mich

Der schnellste Algorithmus,den ich kenne,ist der von Daisuke Takahashi

Der ist auch in meinem Notizbuch.

Den kannst du ja auch mal testen.

Gruss endy






-----------------
Dean Koontz : Zwielicht

Unzählige verschlungene Nachtpfade zweigen vom Zwielicht ab.
Etwas bewegt sich inmitten der Nacht,das nicht gut und nicht richtig ist.

The Book of Counted Sorrows.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1426
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.

Gruß Gerd



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1426
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2021-02-28


Ich habe mir den YMP-Code nochmals angesehen,
und noch eine Multiplikation mit Multitasking gefunden:


Damit sinkt Timing auf 1.38 s und Gesamtzeit auf 3.7 s !!!
14.24 mal schneller als der schnellste Code von GMP!


Das mit Fibtakahashi dauert noch etwas...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1426
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2021-03-01


Kein Internet heute..
Handy, deshalb kurz.
Timing unter 0.8 s!

ab 3.3.2021 wieder Internet -> hier nun das Bild dazu:


Gehe deshalb auf n=5 Mrd
Fibona 21,8s Timing 7,7s
FibTak 18,0s Timing 4s




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1426
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1426
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2021-03-03


Endlich wieder Internet.
Dank der Optimierung sind Argumente um 10^10 kein Problem.


Benchmark Fibonacci(10^10)
YMP Takahashi 20 Threads 38.3 s
YMP ln2       20 Threads 46.1 s
Mathematica12 1 Kern    824.9 s

Hinweis: die einfache RAM-Disk ist relativ langsam (kostenlos, nur NTFS, nicht optimiert). Daher brauchen die etwas über 2 GB etwa 0.9 s.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1426
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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)




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1426
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1857
Herkunft: Thüringen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2021-03-03


Meine Fresse,super ! 👍

[Die Antwort wurde nach Beitrag No.11 begonnen.]


-----------------
zum Primzahl k-Tupel Thread
PDFs on "Mathematik alpha"
Hinweis: MP-Notizbuch



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1426
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.

Grüße Gerd



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1426
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, vom Themenstarter, eingetragen 2021-03-03


Nun habe ich mal das Maximum ausgetestet:
n=2*10^10 = 20 Mrd. siehe Fibonacci-Benchmark
RAM-Verbrauch: 32 GB !! -> nix mit RAM-Disk.



Das Schreiben der 4 GB auf die Festplatte ist mit über 26 s nun langsamer als die HEX-Berechnung (16.5 s).

Grüße Gerd



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]