Antworte auf:  Suche Fibonacci(10^9) Benchmarks von hyperG
Forum:  Numerik & Optimierung, moderiert von: matroid

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 
 


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1465
 Beitrag No.15, eingetragen 2021-03-03 23:30    [Diesen Beitrag zitieren]

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


hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1465
 Beitrag No.14, eingetragen 2021-03-03 18:04    [Diesen Beitrag zitieren]

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


pzktupel
Aktiv
Dabei seit: 02.09.2017
Mitteilungen: 1953
Wohnort: Thüringen

 Beitrag No.13, eingetragen 2021-03-03 17:51    [Diesen Beitrag zitieren]

Meine Fresse,super ! 👍

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


hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1465
 Beitrag No.12, eingetragen 2021-03-03 17:50    [Diesen Beitrag zitieren]

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: 1465
 Beitrag No.11, eingetragen 2021-03-03 17:41    [Diesen Beitrag zitieren]

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: 1465
 Beitrag No.10, eingetragen 2021-03-03 17:29    [Diesen Beitrag zitieren]

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.


hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1465
 Beitrag No.9, eingetragen 2021-03-02 17:37    [Diesen Beitrag zitieren]

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: 1465
 Beitrag No.8, eingetragen 2021-03-01 23:02    [Diesen Beitrag zitieren]

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



hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1465
 Beitrag No.7, eingetragen 2021-02-28 22:15    [Diesen Beitrag zitieren]

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...


hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1465
 Beitrag No.6, eingetragen 2021-02-28 21:27    [Diesen Beitrag zitieren]

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


endy
Senior
Dabei seit: 10.01.2011
Mitteilungen: 3230
 Beitrag No.5, eingetragen 2021-02-28 20:03    [Diesen Beitrag zitieren]

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





hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1465
 Beitrag No.4, eingetragen 2021-02-28 16:16    [Diesen Beitrag zitieren]

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.


hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1465
 Beitrag No.3, eingetragen 2021-02-28 15:50    [Diesen Beitrag zitieren]

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


haegar90
Aktiv
Dabei seit: 18.03.2019
Mitteilungen: 659
Wohnort: Gog

 Beitrag No.2, eingetragen 2021-02-28 12:42    [Diesen Beitrag zitieren]

..war wohl off-topic.


hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1465
 Beitrag No.1, eingetragen 2021-02-28 10:40    [Diesen Beitrag zitieren]

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


hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1465
 Themenstart: 2021-02-27 19:00    [Diesen Beitrag zitieren]

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


 
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]