4 ms·
> 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 so
by jacobolus 7y ago
> 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.
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.
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”.
> They run in constant [...] time
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.
Or alternately we can just precompute and cache the entire set of them if we want. There are only 78.
Here’s a Javascript implementation
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];
- wwweston 7y agoI want to make the same objections (among others) but... interestingly, all of these actually reinforce the author's overarching point, which is less that everyone should be using closed forms for fibonacci and factorial computations, and more that an analytical understanding of conceptual model and computing implementations often matters more than the due generally given. You're able to make the critical evaluation of closed-form solutions using doubles vs other options precisely because you're practicing the approach he's recommending (albeit, apparently, a little bit better!).
- lifthrasiir 7y agoThe GP demonstrates that the mathematics alone cannot produce a good software and does not necessarily refute the OP.
- KUcxrAVrtI 7y agoYou need to know a lot more computers than mathematics to know that floating point numbers are nothing like real numbers, neither are machine implemented integers.
- lifthrasiir 7y agoNot necessarily. Error analysis with floating point numbers is closely related to the mathematics, you have no other way. You can use several heuristics, like avoiding catastrophic cancellations or better summation algorithms, to improve error bounds and there is even an automatic approach like Herbie [1], but ultimately you can't be as sure without error analysis. (Note that the interval arithmetics or unum or posit or whatever are crude but useful approximations to the proper error analysis.) [1] https://herbie.uwplse.org/ https://herbie.uwplse.org/
- posix_me_less 7y ago> Note that the interval arithmetics or unum or posit or whatever are crude but useful approximations to the proper error analysis. "crude but useful approximations" is such a strange view. The purpose of machine-controlled error arithmetics is to give the programmer a powerful language construct that enables evaluation of a function or algorithm for arbitrarily small margin of error, using automatically revised accuracy in the intermediate steps. Error analysis is a math subject that gives us better algorithms. One needs both for hitting that desired margin of error with certainty within as short time as possible.
- 0815test 7y ago> a powerful language construct that enables evaluation of a function or algorithm for arbitrarily small margin of error, using automatically revised accuracy in the intermediate steps. AIUI, this is what "constructive (or 'exact') real numbers" give you, and it's quite computationally-intensive. Error arithmetic/interval arithmetic/etc. are only approximations to it. In many cases people don't even bother with the real deal because they're computing way more than one single result, so roundoff errors can be thought of as just one additional source of noise that is going to be averaged out over many 'steps'.
- 0815test 7y agoAIUI, you don't need to "compute" sqrt5 to high precision in order to use that closed form! Just "adjoin" it to Q and compute symbolically over Q(sqrt5).
- lifthrasiir 7y agoThe computation over Q(sqrt(5)) is essentially identical to the matrix form.
- jacobolus 7y agoYes, and that symbolic computation is the same arithmetic as the original algorithm the author was complaining about. Personally I like the version better where you explicitly work in terms of integers like a + bφ or rational numbers like (a + bφ)/c. https://observablehq.com/@jrus/zome-arithmetic https://observablehq.com/@jrus/zome-arithmetic very handy when working with the symmetry system of the icosahedron. https://observablehq.com/d/cae3fea57d7cf2d4 https://observablehq.com/d/cae3fea57d7cf2d4
- irchans 7y agoNice. Thanks for that.
- dvfjsdhgfv 7y agoMoreover, the C implementation quoted in the article will give a negative -1323752223 after the 46th number (1836311903). So while I understand the author's point, I think this particular example is not a really good choice.
- valw 7y ago> 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. Know what's even faster? Exponentiating a 2x2 matrix of integer coefficients. And again, that's what a bit of math tells you, so I think the point of the author holds.
- jacobolus 7y agoThose are two ways of saying the same thing. If you want to use a fancier algorithm, then fine.
- valw 7y agoThen I might have misunderstood what you meant by "integer-arithmetic recurrence"; my understanding of it was that it was the traditional recursive implementation of Fibonacci, which has much worse complexity than matrix exponentiation, and is not the same algorithm at all.
- jacobolus 7y agoThere are several ways we might try to optimize this calculation. Really depends on the context/constraints. Since the recurrence is always the same we can e.g. use the identities F_{m+n-1} = F_mF_n + F_{m-1}F_{n-1} and F_{m+n} = F_mF_n + F_mF_{n-1} + F_{m-1}F_n to precompute and cache all of the terms for 2^{n-1} and 2^{n}, and then multiply the appropriate ones together to find whatever value we need based on a binary expansion of the index we want to find a fibonacci number for. This is the same idea as fast matrix exponentiation but saves low-level arithmetic and half of the space, because two of the terms in the matrix are basically redundant.
- irchans 7y agoI am wondering if all three methods (sqrt(5) method, 2x2 matrix exponentiation, and jacobolus's power of two method) take approximately the same amount of time --- slightly less than O( log(F_n)*log(F_n)^2) (using Fürer's algorithm for integer multiplication.)