Contest #1: Fibonacci Zahlen

314159265358979

volkard schrieb:

314159265358979 schrieb:

Was meint denn volkard zur Bewertung?

Ich dachte, Werner sollte noch die Kleinigkeit ändern dürfen. Und dann ab zur Abstimmung. Die drei Ensendungen sind ja quasi alle Quatsch und spannen die Ecken des gerade noch Sinnvollen auf. Wäre interessant, wie sich das Publikum da platziert.

Für Codelängenvergleich sollten nur Tokens gezählt werden. Das ist viel Arbeit. Naja, viel weniger Arbeit, wenn die Einsendungen auf Codelänge optimiert sind.

Geht in Ordnung, also Abstimmung? Was soll denn abgestimmt werden?

volkard

314159265358979 schrieb:

Da hier im Forum (meiner Meinung nach) etwas Abwechslung fehlt, möchte ich gerne regelmäßig eine Art "Contest" machen.

Jeder soll in einem gewissen Zeitrahmen ein Programm zur Lösung einer Aufgabe schreiben. Danach wird von den Usern abgestimmt, welches den Contest gewinnt. Es soll das eleganteste Programm bewertet werden, Performance ist nebensächlich.
Die Abstimmung findet nach der Deadline statt, ihr dürft nicht für euer eigenes Programm stimmen. (wäre ja langweilig )

314159265358979

Wenn dir diese Definition von elegant reicht, okay

krümelkacker

Hmm...
Es hat ja gar keiner ausgenutzt, dass

fib(a-1)*fib(b-1) + fib(a)*fib(b) = fib(a+b-1)

gilt. Damit müsste man die Suche nach dem Anfang beschleunigen können. Also, bei extrem hohen Zahlen, müsste sich das lohnen -- zumindest dann, wenn man die Multiplikation auch effizient implementiert.

Wer will denn mal den Fibonacci-Iterator, der hier gezeigt wurde, dahingehend erweitern, so dass folgendes funktioniert:

fibiter a;  for (int i=0; i< 7; ++i) ++a;
fibiter b;  for (int i=0; i<11; ++i) ++b;
fibiter c = indexsum(a,b);
cout << *a << endl; // gibt fib( 7) aus
cout << *b << endl; // gibt fib(11) aus
cout << *c << endl; // gibt fib(18) aus

?

indexsum kann man mit 4 Multiplikationen und 3 Additionen implementieren wenn der Iterator nur ein Paar von aufeinanderfolgenden Fibonaccizahlen speichert. Ich bin ja auch fast geneigt, indexsum nach operator+ umzubennennen, im Sinne der Indizes.

volkard

krümelkacker schrieb:

Hmm...
Es hat ja gar keiner ausgenutzt, dass
fib(a-1)*fib(b-1) + fib(a)*fib(b) = fib(a+b-1)
gilt. Damit müsste man die Suche nach dem Anfang beschleunigen können. Also, bei extrem hohen Zahlen, müsste sich das lohnen.

Daran gedacht hatte ich schon. Aber ich sah auch, daß nur die letzte Addition viel kostet. Die vorletzte nur noch 61% davon. Und die davor nur (61%)² davon. Geometrische Reihe. EIne so schnell schrumpende Reihe hat auch nur eine winzige Summe, vielleicht drei- oder viermal den größen Wert. Aber das war ein Denkfehler. Die Werte schrumfen so schnell. Die Stellenzahlen schrumpfen viel langsamer und anders.

Also mal genauer schludern:
Unter Vernachlässigung von "wenn man die Multiplikation auch effizient implementiert."

Φ sei der goldene Schnitt mit 1.618...
fib(n) ist für große n ungefähr Φ^n.
fib(n) hat ungefähr 0.21*n Stellen.

Ohne Deinen Trick:
So viele Ziffern muß ich addieren für fib(256):
0.21*1 + 0.21*2 + 0.21*3 + ... + 0.21*256 = 0.21 * 256*257/2 = 6908

Mit Deinem Trick: fib(128) hat ungefähr 26 Stellen. Mit Schulbuchmultiplikation bräuchte ich ungefähr 26*26 Additionen, sind 576. Du sagst, man brauch 4 davon. 576*4=2304. Und fib(128) zuz bauen, wäre 0.21 * 128*129/2=1733, zusammen 4037.

Also 40% Einsaprung. Und wenn ich gerade nicht schief gucke, hängen sind überlebenden Ausdrücke proportional zum Quadrat der Stellenzahl, also auch zum Quadrat von n.

Also konstant 40% Einsparung, interessanterweise nicht "Also, bei extrem hohen Zahlen, müsste...".

So ist der Trick also noch nichts wert. Ich glaube, man mußte den Trick auch rekursiv machen UND sowas wie die Karatsuba-Multiplikation nehmen, um in eine bessere Komplexitätsklasse zu fallen.

krümelkacker

Ich hatte das nicht nachgerechnet. Aber mein Gefühl sagte mir, dass das ohne optimierte Multiplikation knapp werden könnte...

Lass mich mal überlegen ... Wie aufwändig ist es, aus einem Paar von aufeinanderfolgenden Fibonaccizahlen mit jeweils n Stellen ein Paar mit jeweils 2n Stellen zu erzeugen?

Methode 1 ("Immer nur aufaddieren"):
Mit Überschlagen komme ich hier auf einen Aufwand von O(n^2)

Methode 2 ("Trick"):
1 Addition (n-stellig + n-stellig = n-stellig)
4 Multiplikationen (zwei n-stellige Zahlen --> 2n-stellige Ergebnisse)
2 Additionen (2n-stellig + 2n-stellig = 2n-stellig)
Alle Additionen sind hier in O(n) berechnebar. Die Multiplikationen aber mit O(n^1.58...) für Karatsuba und O(n*log(n)*log(log(n))) für Schönhage-Strassen. Also, insgesamt per Karatsuba sind's hier O(n^1.585) Operationen.

=> Bei genügend großem n ist der "Trick" unter Verwendung von Karatsuba (oder besser) schneller.

Richtig?

volkard

krümelkacker schrieb:

=> Bei genügend großem n ist der "Trick" unter Verwendung von Karatsuba (oder besser) schneller.

Richtig?

Wenn man sie die vorher benötigten n-stelligen nicht per Iterator besorgt.
Ich fürchte, sich n-stellige per Iterator zu besorgen, kostet bereits 25% der Zeit, die man für 2-n-stellig per Iterator bezahlen müßte.

krümelkacker schrieb:

Wie aufwändig ist es, aus einem Paar von aufeinanderfolgenden Fibonaccizahlen mit jeweils n Stellen ein Paar mit jeweils 2n Stellen zu erzeugen?

Ja, das flutscht.

Mal angenommen, die Stellenzahl des Paares würde sich immer genau verdoppeln.
Das wirft die kleine Frage auf, wie wir ein Paar 61-stelliger Zahlen erzeugen.
Hmm, man kann ja immer, weil man eh Paare hat, auch das Folgepaar bauen.
1 2 3 6 7 14 15 30 60 61
Ja, geht locker. Sogar mit der Garantie, daß mindestens jeder zweite Schritt ein Multiplizier-Schritt mit Stellenverdopplung ist. Ja, das flutscht.

wxSkip

Was wird der nächste Contest? Ein Sudoku-Solver? Und wo steckt eigentlich Werner Salomon?

Kriterien?
-Lesbarkeit (Abstimmung)
-Schönheit (Abstimmung)
-Kürze (Tokens)
-Performance
-Ein Mix (Abstimmung)
-Unleserlichkeit

314159265358979

Sudoku-Solver klingt schon mal gut.
Wie wäre es mit einer Mischung aus Performance und Unlesbarkeit / Kürze?

SeppJ

314159265358979 schrieb:

Sudoku-Solver klingt schon mal gut.
Wie wäre es mit einer Mischung aus Performance und Unlesbarkeit / Kürze?

Nimm doch nicht immer so ausgelutschte Probleme.

314159265358979

SeppJ schrieb:

314159265358979 schrieb:

Sudoku-Solver klingt schon mal gut.
Wie wäre es mit einer Mischung aus Performance und Unlesbarkeit / Kürze?

Nimm doch nicht immer so ausgelutschte Probleme.

Mach doch mal einen Vorschlag

TyRoXx

Spontane Idee: Umsetzung einer kleinen Programmiersprache, mit der sich mathematische Aufgaben lösen lassen. Am Ende gewinnt dann der schnellste Interpreter oder so. Natürlich implementieren alle die gleiche Sprache und das für den Benchmark verwendete Programm ist vorher nicht im Detail bekannt.

314159265358979

Na das klingt doch mal super
Wie gut, dass ich schon eine eigenen kleine Programmiersprache angefangen habe, die könnte ich etwas verändert dann als Aufgabe stellen

camper

Bitte eine compilerfähige Sprache. Dann sind auch TMP-Lösungen denkbar.

314159265358979

camper schrieb:

Bitte eine compilerfähige Sprache. Dann sind auch TMP-Lösungen denkbar.

Daran hab ich auch gedacht

314159265358979

Das einzige Problem dabei: Wie will man eine TMP Lösung mit einer "normalen" vergleichen? Ich vermute, es wird mehr "normale" als TMP Lösungen geben, und bei TMP vielleicht nur deine. Evtl 2 Gruppen?

wxSkip

Wie wäre es denn mit einem modifizierten TicTacToe (vielleicht ein 10*10-Feld, in dem man min. 4 in einer Reihe bekommen muss, damit nicht schon bei einigermaßen guten Algorithmen immer ein Patt herauskommt), bei dem verschiedene Algorithmen (gleiches Interface nach außen) gegeneinander antreten (meinetwegen 1000 mal, der Algorithmus mit mehr Siegen gewinnt). Man könnte natürlich zusätzlich auch Performance, Design, Kürze... bewerten.