Moivre-Binet Formel für größere Zahlen realisieren

[hansjoachim]

Hi,

mit folgender Formel will ich große Zahlen in der Fibonacci-Folge bilden: http://upload.wikimedia.org/math/c/f/9/cf9e689b7872d81c0655a10eaf38aa32.png
Für den kleineren Zahlenbereich lässt sich das relativ einfach realisieren. Ich habe versucht das mit GMP hinzukriegen. Aber da schaff ich es nicht mal richtig 1/wurzel 5 darzustellen. Liegt dass daran dass ich mich nicht genug eingearbeitet habe oder ist das eher das ungeeignete Werkzeug für solche Zwecke? Gibt es eine Alternative, welche vielleicht auch näher an C++ ist als an C?

Vielen Dank

Joachim Redies

[drakon]

Liegt dass daran dass ich mich nicht genug eingearbeitet habe oder ist das eher das ungeeignete Werkzeug für solche Zwecke? Gibt es eine Alternative, welche vielleicht auch näher an C++ ist als an C?

Ich würde mal sagen ersteres.
Und grundsätzlich ist mit C++ alles möglich, was mit C auch möglich ist.

[hansjoachim]

drakon schrieb:

Ich würde mal sagen ersteres.

Leider gibt es aber keine Möglichkeit in der Library Potenzen mit rationaler Basis zuberechnen.

http://gmplib.org/manual/Integer-Exponentiation.html#Integer-Exponentiation
http://gmplib.org/manual/Rational-Number-Functions.html#Rational-Number-Functions

[Werner Salomon]

Hallo hansjoachim,

Die Moivre-Binet Formel hat den Vorteil, dass man den zweiten Summanden getrost weglassen kann, wenn man anschließend wieder auf ganze Zahlen rundet.
Wenn Du dann die Klasse 'Log10' aus diesem Beitrag nutzt, so liefert folgendes kleines Programm Ergebnisse für f_n mit n bis max-int.

#include "Log10.h"
#include <iostream>
#include <cmath>

int main()
{
    using namespace std;
    for( int n; cin >> n; )
    {
        cout << "f_" << n << "= "
            << pow( Log10( (1 + sqrt(5.))/2 ), double(n) )/ sqrt( 5.) << endl;
    }
    return 0;
}

man erhält z.B. folgenden Output

100
f_100= 3.54225e+20
10000
f_10000= 3.36448e+2089
1000000
f_1000000= 1.95328e+208987
2100000000
f_2100000000= 1.49786e+438874044

größere Zahlen sind auch denkbar, aber die Genauigkeit geht dann natürlich irgendwann in den Keller.

Gruß
Werner