Fibonacci's recurrence relation loss of precision on big digits

Question

I'm trying to use the Binet's formula to solve Fibonacci's nth number with an O(1) time complexity.

class Application
{
    static void Main(string[] c)
    {
        Console.WriteLine($"Fib(15) : Expected 610 got : {Fibonacci(15)}");
        Console.WriteLine($"Fib(20) : Expected 6765 got : {Fibonacci(20)}");
        Console.WriteLine($"Fib(100) : Expected 354224848179261915075 got : {Fibonacci(100)}");

        Console.ReadKey();
    }

    private static BigInteger Fibonacci(int n)
    {
        double sqrt5 = Math.Sqrt(5d);
        return new BigInteger((1/sqrt5)*Math.Pow((1 + sqrt5)/2, n) - (1/sqrt5)*Math.Pow((1 - sqrt5)/2, n));
    }       
}

The following example works like a charm for the first two tests, but it fails by a quite huge amount for the third test (result is 354224848179263111168 vs. 354224848179261915075.

I guess it might be a problem with the Math.Pow((1+sqrt5)/2,n) part of my formula, but I tried using the formula using decimal, double, float and BigInteger itself, and the result is never the good one.

Is there a way around my problem or should I accept that I can't do this using Math.Pow?

Edit I tried using BigInteger.Pow, but to use it 1+sqrt5 needs to be a BigInteger too, which makes my code look like this at the end because of castings :

double sqrt5 = Math.Sqrt(5d);
return new BigInteger(1/sqrt5)*BigInteger.Pow(new BigInteger(1 + sqrt5/2), n) - new BigInteger(1 / sqrt5) * BigInteger.Pow(new BigInteger((1 - sqrt5)/2), n);

And all values returned are zeroes.

Use BigInteger.Pow() function. possible duplicate http://stackoverflow.com/questions/4297454/math-pow-is-not-calculating-correctly — Gonzalo.-, Oct 27 '15 at 16:25
In addition to what Gonzalo said, if you're starting with a `double` for the square root of 5, you're going to have limited precision in that number to start with, since the square root of 5 cannot be precisely represented by a base-2 number with a finite number of digits. — StriplingWarrior, Oct 27 '15 at 16:30
I tried using the BigInteger.Pow() too, I added the edit in question. And @StriplingWarrior, I assume this means I can't achieve this formula in the way I'm attempting to do it? — IEatBagels, Oct 27 '15 at 16:32
@TopinFrassi: Yeah, you need to save the BigInteger conversion until the last moment or else you end up losing even more precision by dropping the fraction. I haven't thought enough about it to be certain, but it does seem at a glance like Binet's formula probably can't be applied perfectly with numbers of limited precision. — StriplingWarrior, Oct 27 '15 at 16:39
According to the MSDN article on the `decimal` type, the type has 28-29 significant digits. I really don't think you can do this with a floating point types for large values of N. — Tony Vitabile, Oct 27 '15 at 17:15

score 3 · Answer 1 · answered Oct 27 '15 at 17:05

Using double you always have 15 and a half digits of accuracy. You can not expect more, the output of the integer conversion is only as good as the input.

That is why even Binets formula is not O(1) but O(M(n)) for n bit computations, using that F[n] is smaller than 2^n where M(n) is the cost of multiplication which is also a measure for the cost of exponentiation and logarithm.

Fibonacci's recurrence relation loss of precision on big digits

1 Answers1