> <i>But rarely in these discussions will you find relevant mathematical considerations. If the goal is to compute a Fibonacci number or a factorial, the proper solution is not a recursive function, but rather knowledge of mathematics.</i><p>If you want precise results for large sizes, then the integer-arithmetic recurrence is faster than computing the square root of 5 to very high precision and raising it to the nth power.<p>The author’s “proper solution” might better be named the “naive undergraduate introductory linear algebra student solution”. Or maybe “18th century analytic solution ignorant of computer number formats”.<p>> <i>They run in constant [...] time</i><p>If we are going to artificially limit ourselves to numbers smaller than the precision of e.g. double precision floats, then the integer algorithms might just as well be considered “constant time”, where the constant is just whatever it takes to compute the largest value we are considering.<p>Or alternately we can just precompute and cache the entire set of them if we want. There are only 78.<p>Here’s a Javascript implementation<p><pre><code> const fibcache = [
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,
377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711,
28657, 46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465,
14930352, 24157817, 39088169, 63245986, 102334155,
165580141, 267914296, 433494437, 701408733, 1134903170,
1836311903, 2971215073, 4807526976, 7778742049,
12586269025, 20365011074, 32951280099, 53316291173,
86267571272, 139583862445, 225851433717, 365435296162,
591286729879, 956722026041, 1548008755920,
2504730781961, 4052739537881, 6557470319842,
10610209857723, 17167680177565, 27777890035288,
44945570212853, 72723460248141, 117669030460994,
190392490709135, 308061521170129, 498454011879264,
806515533049393, 1304969544928657, 2111485077978050,
3416454622906707, 5527939700884757, 8944394323791464];
const fibonacci = (n) => fibcache[n];</code></pre>