For Fibonacci numbers we have a nice formula:
$$ \frac{\left(1+\sqrt{5}\right)^n-\left(1-\sqrt{5}\right)^n}{2^{n} \sqrt{5}} $$
We can implement that in Mathematica:
a[n_]:= ((1+Sqrt[5])^n-(1-Sqrt[5])^n)/(2^n Sqrt[5])
a[10] //Expand
(* 55 *)
We need Expand
to get rid of all the $\sqrt{5}$'s in the result. For large n
, expanding gives very large intermediate results and therefore this function becomes very slow.
However, Mathematica can do numerical computations to any precision. So we can overcome the problem by computing a[n]
numerically with a precision at least equal to the number of digits of a[n]
and then rounding the result. That can be done as follows:
b[n_Integer?Positive] := With[{z=((1+Sqrt[5])^n-(1-Sqrt[5])^n)/(2^n*Sqrt[5])},
Round[N[ z, 1+N[Log[10,z]]]]]
b /@ Range[10]
(* {1,1,2,3,5,8,13,21,34,55} *)
Now let us compute a very large Fibonacci number by using this function b
and the built in function Fibonacci
.
n=600000;
r1=b[n]; // RepeatedTiming
r2=Fibonacci[n]; // RepeatedTiming
r1==r2
(*
{0.000068,Null}
{0.0012,Null}
True
*)
I am very sure that some years ago the function b
was slower than the function Fibonacci
. But now (version 10.4 and 11.0) it is much faster. Has Fibonacci
indeed slowed down so much or is this a timing problem?
n = 6*^6
andn = 6*^7
), yourb
is only about half as fast asFibonacci[]
. $\endgroup$