Fibonacci-Coding Wettbewerb: Wer ist der Schnellste?

mj

mj

Technische Administration, Dinosaurier, ,
Mitglied seit
17.10.2000
Beiträge
19.529
Renomée
272
Standort
Austin, TX
Nachdem mir gestern Nacht ein wenig langweilig war und ich meinem Prozessor mal so richtig einheizen wollte ist dabei etwas interessantes rausgekommen - wer mich kennt der weiß, dass ich einmal in Fahrt nicht mehr zu bremsen bin.
Aus der einfachen fib(x) Implementierung in ML ist dann eine einfache Assembler-Implementierung geworden und zum Schluss eine hoch-optimierte Funktion. Die Zeiten sind derzeit im Vergleich zur hochoptimierten ML-Funktion noch sehr gut, wobei letztere bei fib(46) bereits aussetzt.
Jetzt hab ich hier mal zwei Fragen/Aufgaben an die Interessierten / Cracks / Programmierer / Informatiker: Um den fib(46) zu berechnen benötigt mein eigener optimierter Assembler-Algorithmus 37,3 Sekunden, für den fib(42) nur 5.5s. Derzeit läuft grade ein Durchlauf mit fib(61) - bereits seit guten zwei Stunden.

Ich rufe hiermit also alle Cracks/Freaks auf den Algorithmus zu optimieren oder sich selber einen zu überlegen der schneller ist - es wäre doch mal interessant zu sehen wer den schnellsten fibonacci vorlegt. Wer nicht weiß was der fib(x) ist, der findet auf meiner Homepage eine Beschreibung inkl. dem Quelltext der eigenen Implementierung. Wer schafft es mich auf identischer Hardware zu schlagen? Wer schafft es den Quellcode noch zu optimieren oder ein komplett neues Konzept zu erstellen und die Fibonacci-Zahlen noch schneller zu errechnen?

Die Regeln sind hierbei einfach: Es muss unter Linux oder ANSI-Windows laufen (damit ich hier einen Testbench machen kann) womit schon mal sämtliche Visual XXX für Windows ausfallen - natürlich kann es ein ANSI-C Programm sein, schließlich compiliert dies ohne Probleme unter Linux. Die Programmiersprache steht zur freien Wahl, auch Mischcode ist möglich (Inline-Assembler beispielsweise wie in meinem Fall) und der Quellcode muss selber erstellt sein, nicht von irgendeiner Webseite kopiert oder abgeschrieben. Weiterhin muss der Quellcode natürlich zur Einsicht sein, schließlich könnte sonst jeder daherkommen mit einer Tabelle und einem einfachen lookup - das ist jedoch nicht der Sinn der Sache.
Also los, zeigt mir was ihr draufhabt!
 
wie du weißt, schlage ich dich mit meinem ti-89 locker :-) und ich hab was rausgefunden: der macht keinen tabellen lookup, wie zunächst vermutet, viel eher zeichnet er den graphen virtuell und springt dann an die entsprechende speicheraddresse, welche dem x wert zugeordnet ist. (vielleicht auch eine möglichkeit, die pc variante zu beschleunigen.)
 
für fib 50 brauch ich in etwa 4 1/2 sekunden... ich muss mit der stoppuhr daneben sitzen :-)
 
Original geschrieben von D'Espice
Derzeit läuft grade ein Durchlauf mit fib(61) - bereits seit guten zwei Stunden.
!
Zum Vergrößern anklicken....
Hm irgendwie ist deine Zeit extrem lange. Ich hab das mal für Windows programmiert mit c++ und hatte das ganze in 0,01 Sekunden berechnet . Falls es dir was nutzt kann ich bei Bedarf den Quellcode posten.
 
Tach erstmal

also ich bin kein Informatik-Spezialist, aber ... immer offen für neue Dinge.

eine Frage:was soll die Funktion genau berechnen ? von einer gegebenen Fibonacci-Zahl die beiden ersten Zahlen ? z.B. so:
1+1=2
1+2=3
2+3=5
3+5=8
5+8=13
wenn ich also die Funktion fib(13) aufrufen sollte, müsste sie mir 1 und 1 ausspucken ?
oder ..
2+5=7
5+7=12
7+12=19
fib(19) müsste also 2 und 5 ausspucken ?

Danke ... ;)
 
Original geschrieben von Procyon_theEvil
fib(19) müsste also 2 und 5 ausspucken ?
Zum Vergrößern anklicken....
Nein, die Fibonacci - Zahlen sind so definiert:
fib(0) = 0
fib(1) = 1
fib(i) = fib(i-1) +fib(i-2)

fib(19) ist also die Summe von fib(18) und fib(19) ... Um die zu erhalten musst du also alles möglichst geschickt rekursiv durchrechnen...

Edit: würde übrigens auch auf der Homepage von D'Espice stehen ;-)
 
Tach erstmal


aaaaahhhhhso.


also wäre

fib(7) die 7. Fibonacci-Zahl und nicht die Zahl 5 selber ...

fib(7)=fib(6)+fib(5);
fib(6)=fib(5)+fib(4);
fib(5)=fib(4)+fib(3);
fib(4)=fib(3)+fib(2);
fib(3)=fib(2)+fib(1);
fib(2)=fib(1)+fib(0);
fib(1)=1;
fib(0)=0;
also ist
fib(2)=fib(1)+fib(0)=1+0=1;
fib(3)=fib(2)+fib(1)=1+1=2;
fib(4)=fib(3)+fib(2)=2+1=3;
fib(5)=fib(4)+fib(3)=3+2=5;
fib(6)=fib(5)+fib(4)=5+3=8;
fib(7)=fib(6)+fib(5)=8+5=13;

ahso. jetzt verstehe ich.

Programmieren ist also ganz einfach ... optimieren ohne Assembler-Kenntnisse wohl nicht.
 
Tach erstmal

so ich hab mal ein bisschen C++ geschrieben ... ich hoffe es wird lesbar dargestellt ...
[edit]
statt [qu ote] [co de] benutzt
[/edit]
Code: 
#include <iostream>

unsigned long int my_fibonacci(unsigned long int nte_fibonacci_nummer)
    {
    if(nte_fibonacci_nummer==0)
        return(0);
    // ELSE
    if(nte_fibonacci_nummer==1)
        return(1);
    // ELSE
    return(my_fibonacci(nte_fibonacci_nummer-1)+my_fibonacci(nte_fibonacci_nummer-2));
    }

int main()
    {
    unsigned long int fib_number_to_calculate;
    fib_number_to_calculate=1;
    std::cout<<"Fibonacci-Nummern berechnen\n";
    while(fib_number_to_calculate>0)
        {
        std::cout<<"\nWelche Fibonacci-Nummer haetten Sie gern?\n(0=Beenden)\n\t";
        std::cin>>fib_number_to_calculate;
        std::cout<<"Die "<<fib_number_to_calculate<<". Fibonacci-Zahl ist\n";
        std::cout<<"\t"<<my_fibonacci(fib_number_to_calculate)<<"\n";
        }
    std::cout<<"\nAuf Wiedersehen!";
    return(0);
    }
 
Zuletzt bearbeitet:
*lol**lol*

Habs schon - mein Algorithmus braucht für fib(64) 0ms :D

Und das im Interpreter von Visual Basic *lol*


PS Die Lösung ist so extrem einfach, dass man sie fast übersieht.

2504730781961 - das ist fib(61)
 
Zuletzt bearbeitet:
Tach erstmal

mein Programm schafft die 46. Fibonacci-Nummer in ca 1min10sec (ungenau weil Stoppuhr)

Lief auf:
AMD K7 XP 1800+ 1533 MHz
512 MB DDR-RAM 133 MHz
Win2k
MinGW 2.0.0.3 (GCC 3.2, glaub ich)

kann sein dass es nicht die gesamte CPU-Kapazität zur Verfügung hatte
(Opera, Seti, eMule, Winamp, Firewall, Trillian etc)
 
Original geschrieben von intel_hasser
*lol**lol*

Habs schon - mein Algorithmus braucht für fib(64) 0ms :D

Und das im Interpreter von Visual Basic *lol*


PS Die Lösung ist so extrem einfach, dass man sie fast übersieht.

2504730781961 - das ist fib(61)
Zum Vergrößern anklicken....

Meinst du dass ein 32-Bit unsigned Integer nicht ausreicht ?

Oder ist das jetzt ein mathematisches Geheimnis dass man erst im Studium erklärt bekommt ?
 
Das mit dem us32bit hab ich einfach durch den Currency in VB umgangen, der macht bis fib(73) - und da der Currency 4 feste Nachkommastellen hat kann man da auch noch etwas schieben.

Nein, ich meinte eigentlich den Algorithmus - hier ist mal meine Umsetzung. Nur eins schon vornweg: fib(x) ist doch immer konstant - warum also immer neuberechnen?

Code: 
Option Explicit

' fib(fibval)
Public Const fibval = 73
    
' Array, was schon errechnet
Public fibifeval(fibval) As Byte
Public fibeval(fibval) As Currency


' Main
Public Sub Main()
    
    Dim s As Double
    Dim e As Double
    Dim val As Currency
    
    s = Timer
    val = fib(fibval)
    e = Timer
    
    MsgBox CStr(val) + vbCrLf + CStr(Fix((e - s) * 1000)) + "ms time"
    
End Sub


Public Function fib(a As Long) As Currency
    
    ' Wenn !0 !1
    If a > 1 Then
        
        ' Wenn Wert schon berechnet
        If fibifeval(a) <> 0 Then
            fib = fibeval(a)
            Exit Function
        End If
        
        ' Wenn Wert noch nicht berechnet
        fib = fib(a - 1) + fib(a - 2)
        fibifeval(a) = 1
        fibeval(a) = fib
        Exit Function
    End If
    
    If a = 1 Then fib = 1
    If a = 0 Then fib = 0
    
End Function

Wir speichern, wenn wir fib(x) berechnet haben, das Ergebnis einfach in einem Array ab - und voila er muss für fib(61) nur ~61 rechenoperationen ausführen.

Nicht über den saumäßigen Code wundern, das sollte ein erster Test werden ;)

Irgendwo hatte ich schonmal eine kleine Lib geschrieben, die mit Zahlen als Strings umgeht - also praktisch unendlich lange Zahlen unterstütz. Habs aber net mehr gefunden, sonst hätt ich es damit gemacht.
 
Zuletzt bearbeitet:
Original geschrieben von intel_hasser
Nein, ich meinte eigentlich den Algorithmus - hier ist mal meine Umsetzung. Nur eins schon vornweg: fib(x) ist doch immer konstant - warum also immer neuberechnen?
Zum Vergrößern anklicken....
Stimmt. Ich hab das ganze mal auf die Schnelle in Turbo Pascal programmiert, wegen der Zeitmessung. Aber die funzt da nicht zuverlässig ... 2 Sekunden gebraucht für fib(35) aber 30 Sek angezeigt ... :(
 
Code: 
Option Explicit

' Fib(FibVal)
Public Const FibVal = 46

' Gespeicherte Werte
Public FibEval(2) As Currency

' Main
Public Sub Main()

    'Gespeicherte Werte initialisieren
    FibEval(0) = 1                          ' Fib(1)=1
    FibEval(1) = 0                          ' Fib(0)=0


    'Start und Endzeit -> Zeitdauer
    Dim TimeStart As Double
    Dim TimeEnd As Double
    
    'Ergebnis
    Dim Eval As Currency
    
    TimeStart = Timer
    Eval = Fib(FibVal)
    TimeEnd = Timer
    
    MsgBox (CStr(Eval))
    
    
    
    

End Sub


Public Function Fib(x As Currency) As Currency
    Dim i As Currency
    
    If x <= 1 Then Fib = x: Exit Function
    
    For i = 2 To x
        
        'Array um 1 verschieben
        FibEval(2) = FibEval(1)
        FibEval(1) = FibEval(0)
        
        'Fib(i) errechnen
        FibEval(0) = FibEval(1) + FibEval(2)
                    
    Next i
      
    Fib = FibEval(0)

End Function

So, nun hab ich den Algorithmus noch seiner rekursivität beraubt ;)
Mit der String/ZahlenLib sollte es nun möglichsein nahezu beliebig große fib(x) zu errechnen.

PS Mein Algorithmus braucht auch für fib(73) 0 millisekunden ;D - und die Zeit wird richtig gemessen.


*
So, nun hab ich das Ding für praktisch unendlich lange Zahlen portiert.

fib(10000) ist zb. 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

- 2090 stellen, er hat dafür aber schon 9664ms gerechnet (im VB Interpreter)

*
Und nochmal etwas am Algorithmus rumgehämmert - jetzt braucht er 5627ms für fib(10000) im Interpreter, kompiliert dauert es 901ms.

*
820ms kompiliert

*
Und nochmal ein ganzes Eck optimiert - 640ms für Fib(10000) im Interpreter 8)
Kompiliert dauert es noch 220ms.

*
610ms im Interpreter, nun unterstützt er auch die ganz großen Zahlen (vorher nur bis ~4000 Stellen)

*
530ms im Interpreter... aber so langsam ist nicht mehr viel zum optimieren :(

*
520ms im Interpreter - nebenbei auch eine kleine Dummheit beseitig bei der er mit 4mal so viele Stellen wie nötig gerechnet hat.

fib(200000) in 61077ms (kompiliert)
Die Zahl hat 41798 Stellen.
 
Zuletzt bearbeitet:
intel_hasser:
Interessanter Ansatz. Wenn ich das richtig verstanden habe nimmt deine Funktion die Werte aus einem bereits vorinitialisierten Array das bis zu einem bestimmten fib(x) bereits vorberechnete Werte enthält, oder?

Um also fib(x) zu errechnen, müssen davor entsprechend viele Rechenoperationen durchgeführt werden um das Array vorzuinitialisieren oder hab ich an deinem Algorithmus etwas nicht verstanden? Wenn das so ist, dann musst du dieses vorinitialisieren zur Berechnung mit einbeziehen, sonst könnte ich ja einfach die ersten 100,000 Fibonacci-Zahlen in einer Tabelle speichern und einen blitzschnellen Lookup machen - was aber nicht gewollt ist wie ich bereits im ersten Posting sagte ;) Der Trick an diesem Wettbewerb soll ja eine Optimierung der Rekursion sein - wobei nicht zwingend Rekursion verwendet werden muss. Aber ein Tabellen Lookup ist beim Ausgeben schnell, jedoch extrem speicherintensiv und benötigt sehr lange um die Tabelle anzulegen.
Sollte ich jedoch falsch liegen dann klär mich bitte auf, meine VB-Kenntnisse sind mittlerweile doch ziemlich eingerostet.
 
Nein, er berechnet alles selber (und initialisiert garnix ;D)

Also:

wir wollen Fib(10) haben:

wir initialisieren also das Array, aber nur 2 Werte nämlich:
Eval[0]=0 // fib(0)
Eval[1]=1 // fib(1)

und nun rechnen wir:

fib(2)=fib(1)+fib(0) -> fib(2)=eval[1]+eval[0]
Das Ergebis speichern wir in Eval[2]

jetzt kommt fib(3)=fib(2)+fib(1)
fib(3)=Eval[2]+Eval[1]

usw. bis 10.
Das spart sämtliche rekursion und ist verdammt schnell. Inzwischen hab ich auch das mit dem Array noch besser geregelt, so dass das Array nur noch 3 Einträge hat.

PS

jetzt wieder 540ms im Interpreter, allerdings mit Statusanzeige und einer kleinen GUI ;D

*
In meinem Code heist das Array nicht Eval, sondern FibEval.
 
Zuletzt bearbeitet:
OK jetzt hab ich's verstanden *Kopf_an_Wand_donner*
Das ist ein sehr interessanter Ansatz die Fibonacci-Zahlen auszurechnen, ich werd gleich mal schauen wie sich die entsprechende Assembler-Implementierung schlägt. Ach ja, kleiner Denkfehler bei dir: fib(0) = 1 per Definition, nicht wie bei dir angegeben 0 ;)
 
Original geschrieben von D'Espice
Ach ja, kleiner Denkfehler bei dir: fib(0) = 1 per Definition, nicht wie bei dir angegeben 0 ;)
Zum Vergrößern anklicken....

*noahnung* - es funktioniert und die Ergebnisse stimmen *buck*
Ich hab bei mir das Array genau so initialisiert. Oder ist das so eine definition wie x^0=1?

PS Jetzt hab ich ihn auf 64bit umgestellt, rechne also wieder mit Currencies (sind 64bit Variablen).
Auf den Hammer optimiert dürfte das ganz schön speed bringen... ;)
501ms für fib(10000) im Interpreter

Viel Spaß übrigens beim optimieren ;), die jetzige Version unterscheidet sich fast vollständig von der oben angegebenen.

*Kopf_an_Wand_donner*
Zum Vergrößern anklicken....
So gings mir auch. Ist ja eigentlich so einfach der kniff und dann auch noch so wirkungsvoll
 
Zuletzt bearbeitet:
Der Kniff ist der Wahnsinn, geniale Idee. Hätte ich schneller implementiert wenn da nicht meine eigene Dummheit gewesen wäre und ich den Zähler anstatt zu inkrementieren aus Versehen dekrementiert hab :)

Ergbnis sieht wie folgt aus:

fib(46) in 2µs
fib(61) in 3µs
fib(1000) in 12µs
fib(10000) in 164µs
fib(100000) in 2874µs
fib(1000000) in 4881µs

Die Ergebnisse sind unglaublich schnell, ich sag's doch immer wieder: An echtem harten Assembler geht doch nix vorbei. Übrigens ist auch der Code stark optimiert und verwendet sowenig Operationen und Codezeilen wie nur irgend nötig.
Allerdings muss man dazusagen, dass die Ergebnisse ab einem bestimmten Wert falsch angezeigt werden - ich vermute eine binäre Darstellungsgrenze. Ich werde es bei Gelegenheit mal über die 64-bit SPARCs an der Uni jagen - vielleicht schaff ich es ja das Programm zu portieren.

Hier noch der Assembler Quellcode:
Code: 
GLOBAL fibonacci


fibonacci:

	PUSH EBP
	MOV EBP, ESP
	MOV EAX, [EBP+8]

	MOV EDI, 1						; tmp-var 1
	MOV ESI, 1						; tmp-var 2
	MOV EDX, 2						; fib-zähler

	call fib1

	MOV EAX, ESI
	POP EBP
	RET

fib1:
	CMP EAX, EDX
	JG fib
	RET


fib:
	MOV EBX, EDI
	MOV ECX, ESI
	ADD EBX, ECX
	MOV EDI, ECX
	MOV ESI, EBX

	INC EDX
	call fib1
	RET
Die Rekursion wird wohl bei Assembler nicht oder nur schwer rauszubekommen sein, schließlich handelt es sich hierbei um keine Hochsprache.
 
Na mein jetziger Algorithmus sieht so aus:

3 Variablen, a1, a2 und a3

Initialisierung:

a2=fib(1) bzw. 1
a3=fib(0) bzw. 0

so, nun berechnen wir

a1=a2+a3 -> das entspricht fib(2)

jetzt schieben wir die Werte im Array

a3=a2 -> a3=fib(1)
a2=a1 -> a2=fib(2)

und nun berechnen wir wieder

a1=a2+a3 -> fib(3)=fib(2)+fib(1)


Und das solange bis a1 dem gewünschten Fib entspricht.



PS Bist du dir wirklich sicher, dass die Werte da oben in µs sind? Wie hast du fib(1000000) errechnet, die Werte sind ja längst größer als 32bit, oder 64bit ( fib(10000) ist ein 9536bit Wert).

Oder hast du das einfach vergessen und den oberen Teil abgeschnitten? ;)
(Das würde die wirklich sensationell kurzen Zeiten erklären)
 
Ich bin mir sehr sicher dass die Werte in µs sind, die Anzeige des C-Programms sind u_sec - schlag mich tot falls ich mich irre.
Und wie ich sagte, die Werte werden nicht korrekt angezeigt aber die Rechenzeit lässt auf eine korrekte Berechnung vermuten. Da wir keine Rekursion oder verschachtelte Rekursion oder sonstiges haben sondern einen linearen Ablauf lässt sich das ja leicht errechnen.

Bei mir sieht's übrigens sehr ähnlich aus, ich hab auch drei Variablen verwendet, EDI und ESI zum speichern des vorherigen und des vor-vorherigen Ergebnisses, EDX als Zähler sowie EBX und ECX als temporäre Register zum Rechnen - hier hätte ich mir auch eines sparen können und direkt auf EDI und ESI rechnen können - aber mich kennzeichnet vor allem eine Eigenschaft: Faulheit. So war es intuitiver zu schreiben ergo bleibt's so :)

@netburster:
Dank intel_hasser's Trick geht jetzt fib(50) in 3µs ;) Da kann dein Taschenrechner schon mal garnix dagegen ausrichten
 
Du rechnest ja dann mit 32bit Werten - bei 9536bit für fib(10000) lässt du dann ziemlich viele Stellen weg und ergo verkürzt sich die Rechenzeit enorm.

Und das erklärt wohl auch die wirklich kurzen Zeiten (die für fib(x), x<=46 aber noch stimmen sollten - also Netbusters (nicht netburster ;)) Taschenrechner ist Schnee von gestern ;D ;))
 
Die Werte verkürzen sich, das ist richtig, der Rechenaufwand aber bleibt
hmmm *grübel* die x86-FPU hat eine deutlich höhere Genauigkeit als die ALU... ich hab da mal eine Idee
 

Ähnliche Themen

pipin
Western Digital baut seine Position auf dem Gebiet der HDD-Kapazität aus und setzt seine Festplatten-Technologie für Rechenzentrumslösungen für be
Antworten
0
Aufrufe
1K
pipin
pipin
heikosch
Gleicher Preis bei AMD und Intel - wer bietet mehr fürs Geld?
Antworten
0
Aufrufe
71K
heikosch
heikosch
Dr@
Fujitsu STYLISTIC Q572 mit AMD Z-60 APU
Antworten
0
Aufrufe
52K
Dr@
Dr@
Dr@
Bericht: x264 mit OpenCL-Beschleunigung
Antworten
0
Aufrufe
44K
Dr@
Dr@
MusicIsMyLife
ASUS SABERTOOTH/GEN3 R2.0
Antworten
0
Aufrufe
42K
MusicIsMyLife
MusicIsMyLife
Zurück
Oben Unten