Fibonacci-Reihen-Template
-
Warum geht das bei großen Zahlen nicht mehr? Gibts da Überläufe oder ist das ein Fehler?
#include <iostream> template<unsigned num> struct FibonacciNumber { static unsigned const value; operator unsigned() const { return this->value; } }; template<unsigned num> unsigned const FibonacciNumber<num>::value = FibonacciNumber<num - 1>::value + FibonacciNumber<num - 2>::value; template<> unsigned const FibonacciNumber<0>::value = 0; template<> unsigned const FibonacciNumber<1>::value = 1; int main() { std::cout << FibonacciNumber<xxx>() << std::endl; }Wie kann man das besser machen?
-
das liegt an den vielen aufrufen.
und es ist lösbar.
-
ich glaub, der compiler compiliert sich da tot, da da so viele templateinstanzierungen sind. Metaprogrammierung is eben nur was für die ganz harten compiler. Wenn du unbedingt den Wert der Zahl schon vor der laufzeit haben willst, berechne sie doch vorher mit nem programm und füg sie in deinen quelltext ein. Oder wozu braucht man sonst dieses konstrukt?
-
ich glaub, der compiler compiliert sich da tot, da da so viele templateinstanzierungen sind. Metaprogrammierung is eben nur was für die ganz harten compiler. Wenn du unbedingt den Wert der Zahl schon vor der laufzeit haben willst, berechne sie doch vorher mit nem programm und füg sie in deinen quelltext ein. Oder wozu braucht man sonst dieses konstrukt?
Nein. Dieses Vorgehen halte ich für sehr umständlich und riskant. Durch das manuelle Einfügen in den Quelltext wird eine unnötige Fehlerquelle gemacht.
Die Lösung via Metaprogrammierung finde ich deutlich ansprechender. Zurück zu dem Problem. Der Compiler beschwärt sich mit folgender Meldung:
main.cpp:10: error: template instantiation depth exceeds maximum of 500 (use
-ftemplate-depth-NN to increase the maximum)Ich denke der Fehler wird dadurch selbsterkälrend. Der Aufruf
g++ -ftemplate-depth-1000 main.cpp
erhöht die Verschachtelungstiefe und es tritt kein Fehler mehr auf. Jeder gute Compiler sollte ein solches Parameter besitzen mitdem sich die Schachtelungstiefe einstellen lässt.
-
Wie wär's mit
template <int a, int b, int n> struct Fibonacci { enum { value = Fibonacci<b, a+b, n-1>::value;} }; template <int a, int b> struct Fibonacci<a,b,0> { enum { value = b; } };Ungetestet und vermutlich falsch. Dafür braucht's nur lineare Instanziierungtiefe und nicht exponentiell. Mag wer den Code so reparieren, daß er auch funktioniert?
edit: Aufruf: Fibonacci<1,1, 7>::value liefert die 7-te Fibonaccizahl.
-
Als Programmier-Neuling verstehe ich zwar nur die Hälfte hier, aber wnen ich es richtig verstanden habe wird da etwas wegen der rekursiven Fibonacci Formel zuviel Verschachtelt, ist das korrekt?
Wenn ja kann man doch die explezite Fibonacci-Formel nutzen, oder wird dies durch irgendetwas verhindert (vielleicht durch die enthalten wurzeln oder so...)?
-
lucky_tux schrieb:
Die Lösung via Metaprogrammierung finde ich deutlich ansprechender.
Wenn man sich die Kompilierzeit leisten kann.
-
Shinja schrieb:
Als Programmier-Neuling verstehe ich zwar nur die Hälfte hier, aber wnen ich es richtig verstanden habe wird da etwas wegen der rekursiven Fibonacci Formel zuviel Verschachtelt, ist das korrekt?
Wenn ja kann man doch die explezite Fibonacci-Formel nutzen, oder wird dies durch irgendetwas verhindert (vielleicht durch die enthalten wurzeln oder so...)?
das geht ned gut, da c++ templates atm nur integer und typen nehmen dürfen
-
r0nny schrieb:
das geht ned gut, da c++ templates atm nur integer und typen nehmen dürfen
das ist kein problem. wenn sich mathematiker die reellen zahlen aus basteln können, dann kann das ein geübter metaprogrammierer erst recht.
-
Es gibt eine Erweiterungen der Boost.MPL im Vault unter "Template Metaprogramming" -> mpl_math.zip, die auch "Reelle" Zahlen versteht. Damit die explizite Formel zu berechnen ist aber wahrscheinlich (für die sinnvollen Zahlenbereiche) aufwendiger und langsamer als die lineare Version. Ich probiers mal.
