Contest #1: Fibonacci Zahlen
-
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?
-
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.
-
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
-
Sudoku-Solver klingt schon mal gut.
Wie wäre es mit einer Mischung aus Performance und Unlesbarkeit / Kürze?
-
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.
-
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
-
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.
-
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
-
Bitte eine compilerfähige Sprache. Dann sind auch TMP-Lösungen denkbar.
-
camper schrieb:
Bitte eine compilerfähige Sprache. Dann sind auch TMP-Lösungen denkbar.
Daran hab ich auch gedacht
-
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?
-
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.
