Upper limits for fibonnacci

Question

I was reading about the DP version of fibonnaci.
In Sedgewick I saw:
int[] T = new int[47]; for storage of the previous calculations. Elsewhere I saw that the max input for fibonacci should be less than 92.
It is not clear to me how does these numbers come up? I understand that it has to do with overflow and size of int but I am not clear how we end up with these limits.
Any help?

Answer 1

There is a closed-form expression for the n-th Fibonacci number, Binet's formula,

F(n) = (φ^n - ψ^n) / (φ - ψ)

where

φ = (1 + √5)/2;  ψ = 1 - φ = -1/φ

Now |ψ| < 1, so the ψ^n term converges to 0 pretty fast, hence in estimating the size of F(n) it can be ignored except for the first few numbers.

So if you have an integer type with b bits used for the representation of positive integers, you can represent the Fibonacci numbers with

F(n) < 2^b

(since the maximal number that can be represented is 2^b - 1). Ignoring the ψ^n term and using φ - ψ = √5, we find the condition

    φ^n < 2^b * √5
<=> n*log φ < b*log 2 + 1/2*log 5
<=> n < b*(log 2 / log φ) + 1/2*(log 5 / log φ)

log 2 / log φ ≈ 1.44042009 and 1/2*(log 5 / log φ) ≈ 1.672275938, so with a signed 32-bit integer type (which has 31 bits to represent positive numbers, since one bit is used for the sign), you can represent the Fibonacci numbers for

n < 31*(log 2 / log φ) + 1/2*(log 5 / log φ) ≈ 44.65 + 1.67 ≈ 46.32

i.e. the 47 Fibonacci numbers with index between 0 and 46 (inclusive). With an unsigned 32-bit integer type you could also represent F(47).

With a signed 64-bit integer type, you can represent the Fibonacci numbers for

n < 63*(log 2 / log φ) + 1/2*(log 5 / log φ) ≈ 90.75 + 1.67 ≈ 92.42

and with an unsigned 64-bit integer type You can also represent F(93).