Die Mathe-Redaktion - 20.06.2018 05:40 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Juli
ListenpunktFormeleditor fedgeo
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 246 Gäste und 5 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Matroids Matheplanet Forum Index » Aktuelles und Interessantes » Fibonacci-Rennen
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Fibonacci-Rennen
rlk
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.03.2007
Mitteilungen: 10284
Aus: Wien
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-02-28


Hallo,
bei einer Veranstaltung im National Museum of Computing in Bletchley Park versuchten die Teilnehmer mit zum größten Teil historischen Rechnern möglichst viele Glieder der Fibonacci-Folge in 15 Sekunden zu berechnen.

Vielleicht wollt ihr es auch versuchen und staunen, wie schnell moderne Rechner sind?

Servus,
Roland



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 435
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-03-03


Hallo Roland,

als ich las: "..which found 6843 numbers in the sequence in the allotted 15 seconds" musste ich sofort an Pari/GP denken:
Pari/GP
aA=vector(945000);g=1;wt=getwalltime();while((getwalltime()-wt)<=15000,aA[g]=fibonacci(g);g++;);print1(g " " aA[1] "\n");print1(g " " aA[300] "\n")

ergibt
Pari/GP Output
117887 1
117887 222232244629420445529739893461909967206666939096499764990979600

Also ohne Optimierung und nur mit 1 belasteten Kern 117887 Fibonacci-Zahlen!
Nur die 300. Fibonacci-Zahl habe ich zur Kontrolle ausgegeben. Allein die Ausgabe hätte Minuten gedauert. Oder zählt die Ausgabe mit dazu?

Mit Optimierung ist etwa das 10-fache drin.

Fibonacci(100000000) kann man sich unter
Umkehrfunktionen Rechner herunterladen.
Fibonacci(1000000000) habe ich auch, aber noch nicht online.



  Profil  Quote  Link auf diesen Beitrag Link
piquer
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.06.2013
Mitteilungen: 395
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2018-03-03


Hallo Roland,

eine sehr schöne Idee, auch wenn ich zu jung bin, um mit den genannten Rechnern gearbeitet zu haben. Ich habe folgendes mit der GMP-Bibliothek implementiert:
C
  1. #include <gmp.h>
  2. #include <stdio.h>
  3. #include <time.h>
  4.  
  5. int main(int argc, char *argv[])
  6. {
  7. clock_t begin = clock();
  8. clock_t end = begin + 15*CLOCKS_PER_SEC;
  9.  
  10. mpz_t fib[3];
  11. mpz_init(fib[0]);
  12. mpz_init(fib[1]);
  13. mpz_init(fib[2]);
  14.  
  15. mpz_set_ui(fib[0], 1u);
  16. mpz_set_ui(fib[1], 1u);
  17.  
  18. size_t n = 0;
  19. clock_t current;
  20.  
  21. do{
  22. n++;
  23. mpz_add(fib[(n+2)%3], fib[(n+1)%3], fib[(n+0)%3]);
  24. current = clock();
  25. }while(current < end);
  26.  
  27. printf("%zu\n",n);
  28.  
  29. mpz_clear(fib[0]);
  30. mpz_clear(fib[1]);
  31. mpz_clear(fib[2]);
  32.  
  33. return 0;
  34. }

Die Ausgabe schankt etwas, den maximalen Wert, den ich erreichen konnte, war
Bash
#In
gcc -Wall -O3 -march=native fib.c -o fib -lgmp -lm
./fib
#Intel(R) Core(TM) i5-6500 CPU @ 3.20GHz
2247320

Damit lande ich beim 19-fachen von Gerds Wert.

Viele Grüße
Torsten



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 435
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-03-03


Super Torsten,

das ist schon mal eine gute Optimierungsstufe.

Allerdings fehlen mir 3 wichtige Punkte, die wir - aus Gerechtigkeit zu den alten PCs dort - beachten sollten:

1. Ich kenne zwar die genaue Aufgabenstellung nicht, aber die Ergebnisse sollten wenigstens in einem Array zwischengespeichert werden
(für spätere Ausgabe oder Kontrolle auf Richtigkeit; bei solch großen Zahlen spielt RAM-Größe & Geschwindigkeit eine messbare Größe/Grenze)

2. Validierungsberechnung:
Fibonacci(2247320)=5.6780809533095822... e469661
Oft habe ich bei GMP oder Mpfr erlebt, dass zwar ein Ergebnis heraus kam, aber nur bis zu einer Grenze (je nach Funktion um die 300 Mio.) war es richtig.

Mit
mod 1000000000000000000 =731792413363165365 könnte man wenigstens die letzten Stellen vergleichen.

3. Eigentlich müsste man das letzte Ergebnis immer abziehen, da ja die
while-Schleife erst bei Überschreitung endet, und bei exakt 15s
die letzte Berechnung ja noch "am Rechnen" war.



  Profil  Quote  Link auf diesen Beitrag Link
kurtg
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 27.08.2008
Mitteilungen: 1024
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2018-03-03


Kann man das parallelisieren, z.B. mit Matrixmultiplikationen?



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 435
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-03-03


Die reine Iterations-Addition, die immer erst weiterlaufen kann, wenn ein Ergebnis vorliegt, lässt sich nicht parallelisieren.

ABER es gibt mehrere Abkürzungs-Algorithmen, wo man
Zwischenpunkte berechnen kann und die Lücken mit parallelen Prozessen füllen kann:

Beispiel mit 3 Prozessen:

a[1]=Fibonacci(1 Mio)
a[2]=Fibonacci(2 Mio)

Starte 3 Prozesse parallel je 1 Mio. Werte:
FülleArray(0,1)
FülleArray(1,a[1])
FülleArray(2,a[2])

Dann hat man theoretisch pro Thread nur 1 Mio. Werte zu berechnen und kommt mindestens bis 3 Mio.

Einer der vielen "Abkürzungs-Algorithmen" sieht z.B. so aus:
Julia
function fib(n)
   F = BigInt[1 1; 1 0]
   Fn = F^n
   Fn[2, 1]
end

was ja der Matrix-Multiplikation entspricht.
Zum Füllen großer Arrays ist er aber nicht geeignet!



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 435
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2018-03-03


Mein i7 mit Belastung der anderen 6 Kerne schafft aktuell nur

1937125 (ohne Turbo Modus)

Die Validierung ist OK:
Mod= 5564079960297106273011749625 stimmt 97106273011749625

Parallelisierung in Arbeit.



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 435
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2018-03-04


15 s Zwischen-Version ohne RAM-Array (d.h. eigentlich wird nur der letzte Wert berechnet!):
i7-33770K 3,5 GHz Nebenlast     fibonacci(1937125)
i7-33770K 3,5 GHz Turbo GMP_V6b fibonacci(2116159  Mod 10^n = ...435643908182390941 
i5-6500 C 3.2 GHz GMP?          fibonacci(2247320) {mod 10^n = .731792413363165365}
i9-7900X 4,19 GHz GMP_V6b       fibonacci(2425969) Mod 10^n = .. 955783580112324769
i7 Abkürzungs-Algorithmus:      fibonacci(2425969) Mod 10^n = .. 955783580112324769 in  0.0310 s
i7 Abkürzungs-Algorithmus:      fibonacci(24259690) Mod=       ..156424377883778295 in  0.1400 s
...
Validiert mit www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php
Fibonacci mod N=1000000000000000000 = Ergebnis

Aber weg von Abkürzungen, wir wollen ja ehrlich & fair alle Werte zwischenspeichern.
Also Speicherung im RAM-Array...



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 435
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2018-03-04


So, RAM-Array mit den Ergebnissen gefüllt:
i7 mit 16 GB RAM
16 GB Grenze: n=597189  in  8.0030 s

Solange 1 Kern innerhalb der 15 s
Grenze die RAM-Grenze erreicht, braucht man keine Parallelisierung!

Also Umstieg auf den großen i9 mit 32 GB RAM...

Ich melde mich...



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 435
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2018-03-04


Ich habe mir noch die Bilder des Rennens angesehen:
Es wurde IMMER auf Bildschirm ausgegeben, also in die Konsole
übertragen (Betriebssystem-Grafikkarte-Konstrukt).
Danach schaffen heutige PCs etwa 17953 Fibonacci-Zahlen:
Windows-Consolenausgabe
10600348002543799858374135510480679199652590092386227916456878530434652956790225
36114685530320673551254419113841466047669599828571510109755599886334783869862514
93548215877223151706012345939153352158867669120065881143512292581298672288991815
27070319637376722551813874845761500995286188833824647127322587683969947885529409
49878305998577007974217222763988399747061633521186717056003000217685711104256543
86493885768325896463606892238533511664980850579126962672893095279659555446519322
49501524039005192662692522900727054580868509725837726064444169291485203622198054
71173826491410946799712109862369616987310217269585708886895427113851405491457655
99124892155807198110435472503388602068744827749990597310539236381099274498811408
39568405490047602980721759097201739574938341703010117254382744993244124385022521
95679500639883770142753068675308458289202495742052419234627695907280501570465997
82805720851870302967849511936624241908852424881435495214714192405343173
36364883823532828359726801166577325641679461932768189252281633497597436271565042
....
83137721143179797396218407447040666867535315746364314845921599746702720267148173
48389270010239866363879888083659694068173935865136536523902414615224372019877778
48068058645894199234566685781299599719960620437773232463201270441975079594169970
983305096963276290047171725646527496177728969525050004441161302375163073
17953  Mod= 441161302375163073 in 15.0090 s

ABER die Win-Console kann nicht bis zum Anfang zurückgescrollt werden
(nächste Begrenzung)! Man sieht nur die letzten großen Zahlen!

Kennt jemand andere Möglichkeiten:
1.  ALLE Ergebnisse auszugeben
2.  schnell die Ergebnisse auf den Bildschirm (in Grafikkarte) zu bekommen?
DirectX müsste so etwas können...

Beim i9 könnte ich 20 Consolenfenster parallel rechnen lassen und bei
17000 pro Fenster ist man bei 340000 Zahlen -> also weit unter dem RAM-Array.

Aber ich gehe mal davon aus, dass RAM-Array reicht und man einen Art Viewer basteln darf, mit dem man nach den 15 s alle Werte anzeigen kann.

Also weiter mit mehr RAM...



  Profil  Quote  Link auf diesen Beitrag Link
piquer
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.06.2013
Mitteilungen: 395
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2018-03-05


Hallo Gerd,

du hast recht.Ich habe deine Vorschläge teilweise umgesetzt. Wenn man die Ausgabe hinzufügt, schafft mein Programm nur noch rund 95,000 Fibonacci-Zahlen.
C
  1. #include <gmp.h>
  2. #include <stdio.h>
  3. #include <time.h>
  4.  
  5. int main(int argc, char *argv[])
  6. {
  7. clock_t end = clock() + 15*CLOCKS_PER_SEC;
  8.  
  9. mpz_t fib[3];
  10. mpz_init(fib[0]);
  11. mpz_init(fib[1]);
  12. mpz_init(fib[2]);
  13.  
  14. mpz_set_ui(fib[0], 1u);
  15. mpz_set_ui(fib[1], 1u);
  16.  
  17. gmp_printf("%Zu\n",fib[0]);
  18. gmp_printf("%Zu\n",fib[1]);
  19.  
  20. size_t n = 2;
  21. while(clock() < end){
  22. mpz_add(fib[n%3], fib[(n-1)%3], fib[(n-2)%3]);
  23. gmp_printf("%Zu\n",fib[n%3]);
  24. n++;
  25. }
  26.  
  27. fprintf(stderr,"%zu\n",n);
  28.  
  29. mpz_clear(fib[0]);
  30. mpz_clear(fib[1]);
  31. mpz_clear(fib[2]);
  32.  
  33. return 0;
  34. }

Viele Grüße
Torsten



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 435
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2018-03-05


Was hast Du denn für eine schnelle Console: 5 mal schneller als Win 7 ?

Oder ist das Linux? Kann man damit auch bis zur 1. Zahl zurückscrollen?


Ich habe nun das 32 GB-RAM-Array fertig:
cpp 32 GB RAM 1 Thread
InitArray...
do{
		n++;
		mpz_add(fib[(n+2)%3], fib[(n+1)%3], fib[(n+0)%3]);
		mpz_set(aA[n],fib[(n+2)%3]);
		current = clock();
}while(current < end);
clock()
...
beliebige gmp_printf("%Zu\n",aA[??]);

Fibonacci(841933); Validierung: Mod= ...2458708437353 in 15.0000 s

Mit etwas Optimierung könnte man bei 32 GB RAM (oder natürlich noch mehr RAM) sicherlich über die 1 Mio. kommen.

Mit einem Viewer könnte man sich dann im Anschluss alle Zahlen in Ruhe anschauen oder speichern.

Parallelisierung lohnt erst mit noch mehr RAM.

Interessant: Win10 beginnt am Ende der Berechnung mit einer RAM-Komprimierung: ich warte ja am Ende auf Tastatureingabe und wunderte mich, dass langsam mehr RAM frei wurde :-)



  Profil  Quote  Link auf diesen Beitrag Link
piquer
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.06.2013
Mitteilungen: 395
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2018-03-05


Hallo Gerd,

ich nutze Linux. Dort kann ich im Termial (genauer xfce4-terminal) den "unbegrenzten Bildlauf" einstellen, mit dem ich bis zur ersten Fibonacci-Zahl zurückscrollen kann. Ein einface Möglichkeit, die Ausgabe aus dem Termial mitzuschneiden, bietet das Programm "tee" unter Linux:
Bash
#Compile
gcc -Wall -O3 -march=native fib.c -o fib -lgmp -lm
#In
./fib | tee out.dat
#Out
....469210725431764671426
 
#In
du -h out.dat
#Dateigröße
1023M	out.dat
 
#In
wc -l out.dat
#Anzahl der berechneten Fibonacci-Zahlen
101301 out.dat

Viele Grüße
Torsten



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 435
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2018-03-05


Hallo Torsten,

"unbegrenzten Bildlauf" dürfte dann aber auch den RAM-Verbrauch stark ansteigen lassen...

Das bringt mich gleich auf eine Idee, wie man "legal" trotz der 32 GB-Grenze noch mehr Zähler für dieses "Rennen" bekommen könnte:
2 EXE per BAT parallel starten:
- die erste schafft ja 841933 ins RAM-Array
- eine 2. exe könnte mit dem Abkürzungs-Algorithmus erst Fibonacci(841933) und dessen Vorgänger berechnen (unter 0,1 s) und dann Folgewerte auf der Console ausgeben, die ja unter Win speicherbegrenzt ist.
Natürlich liegt man bei beiden etwas unter dem Spitzenwert, aber geschätzte
841800 + 17200 = 859000 könnten es werden.

Eine RAM-Komprimierung zur Laufzeit wird zu umständlich.

Speicherung in externe Medien würde vermutlich nichts bringen:
a) fehlende Cache-Speicher, da der RAM völlig belegt ist
b) zu langsam, wenn man nur winzige Blöcke zur Laufzeit speichern will (32 GB in 15 s = 2,2 GB/s so nicht möglich, da die Variablen vom Typ mpz_t ja auch noch in Strings gewandelt werden müssen)

Meine LAN-Verbindung zum 2. PC (der mit einer DLL den dortigen RAM befüllen könnte) schafft nur 1 MB/s (Faktor 2200 zu langsam)...

Also mehr RAM kaufen :-)
... ohhh, neee: 400 € für nochmals 32 GB - das wird zu teuer.

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



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 435
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2018-03-13


Nun eine große Liste:
Fibonacci-Benchmark-Race

@piquer: habe Dich auch mit aufgenommen. Wenn Du willst, können wir auch Bilder hinzufügen.



  Profil  Quote  Link auf diesen Beitrag Link
rlk 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-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]