He, he, he. Rolls Royce? Yes, it probably is.
If phi is the golden ratio, then we have
phi = (1 + sqrt(5))/2;
F = @(n) (phi^n - (-phi)^(-n))/sqrt(5);
For example, the 12th Fibonacci number is:
It is not truly exact, at least not in terms of floating point numbers. But we need to learn to know when to trust a number to be an integer or not. This is an essential part of computing.
F(12) - 144
ans =
5.6843418860808e-14
I can verify that 144 value using my Rolls Royce engine.
Note that for n reasonably large, we get a very good approximation by ignoring the second term in that formula. For example...
format long g
phi^12/sqrt(5)
ans =
144.001388875493
So a good approximation for the largest Fibonacci number that does not exceed some value k will be simply obtained by taking the log of that expression, and solving for n.
n_k = @(k) floor(log(k*sqrt(5))/log(phi));
n_k(145)
ans =
12
n_k(143)
ans =
11
For larger values of k, say 10^23,
n_k(1e23)
ans =
111
fibonacci(111)
ans =
70492524767089125814114
fibonacci(112)
ans =
114059301025943970552219
You will find that the formula works quite well even for small k.
Best Answer