What is the largest Fibonacci number that can be represented exactly as a MATLAB double-precision quantity without roundoff error?

Another question :

What is the index of largest Fibonacci number that can be represented approximately as a MATLAB double-precision quantity without overflowing ?

   function f = fibonacci(n)
%FIBONACCI  Fibonacci sequence
%   f = FIBONACCI(n) generates the first n Fibonacci numbers.
f = zeros(n,1);
f(1) = 1;
f(2) = 2;
for k = 3:n
   f(k) = f(k-1) + f(k-2);
end

I tried out those :

fibonacci(10^4)
fibonacci(10^3)
fibonacci(10^3+999)
fibonacci(10^3+100)
fibonacci(10^3+400)
fibonacci(10^3+800)
fibonacci(10^3+700)
fibonacci(10^3+600)

fibonacci(10^3+500)
fibonacci(10^3+480)

Finally ,I found when n=1457 is the largest index fn=1.0e+308 *1.306989223763399 is the largest Fibonacci number that MATLAB can represented . but I think this solution is not good enough because is too silly to try and error.

so There must be a better way ~!!

Answer 1

[John D'Errico]

Trivial. Use Binet's formula, knowing that the largest number representable as a double as an integer is 2^53 - 1. I'll look in in the morning to see if you need more.

Edit:

Note, that when I said to use the Binet formula, you need to be careful. So many things can be viewed as obscure tricks in mathematics, until you have seen that trick before. Then it is obvious.

We can write the formula as

F(n) = (phi^n - (-phi)^(-n))/sqrt(5)

where phi is the golden ratio.

phi = (1 + sqrt(5))/2 = 1.618...

The negative power means we will need that second term very little for large enough n, certainly so if all we need to compute which Fibonacci number is close to 2^53 - 1. What happens if we just drop it? So for large n, a VERY good approximation to the nth Fibonacci number (F(n)) is just

F(n) ~ phi^n/sqrt(5)

In fact, that approximation will be quite adequate for your purposes. And if it is adequate, then a simple log and some basic arithmetic will serve to compute the value of n that would yield the largest Fibonacci number that does not exceed 2^53-1.

[Alfonso Nieto-Castanon]

just to clarify John's exactly correct answer, the largest double precision floating point number that you can represent is 2^1024 (see help realmax ), but that does not mean that you can compute up to the 1476th Fib number using double precision numbers. In practice the resolution-spacing for numbers above 2^53 is larger than 1 (see help eps), which means that you cannot uniquely identify an integer above that value using double precision numbers (so the highest you can really get is just the 78th Fib number; you could get just a bit higher using uint64 numbers, and a lot higher using java BigInteger, John's vpi, symbolic toolbox, etc.)

EDIT: added a few more references

[Roger Stafford]

Actually every double precision floating point number greater than 2^53-1 must be an integer and there are a great many of them. It is the reverse that is untrue - not all integers greater than 2^53-1 can be represented as a double. Many are skipped, starting with 2^53+1. As it turns out, the very first fibonacci number that exceeds 2^53-1 cannot be represented as a double. Here's a hint: In decimal it should end in ...221 but instead ends erroneously in ...220 if computed as the sum of the previous two fibonacci numbers.