Comment by jacobolus | Hacker News Reader

Comment by jacobolus | Hacker News Reader

> 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];

I 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!).

The GP demonstrates that the mathematics alone cannot produce a good software and does not necessarily refute the OP.

You 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.

Not 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/

> 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.

> 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'.

I agree, interval arithmetics/unums/$other_fancy_number_concept is just a start, not the end of getting reliable results. However, the roundoff errors that FPU generates are hardly controllable. In general they are not just a simple noise that cancels out on averaging. And some calculations do not do averaging at all.

Moreover, 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.

AIUI, 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).

The computation over Q(sqrt(5)) is essentially identical to the matrix form.

Yes, 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 very handy when working with the symmetry system of the icosahedron. https://observablehq.com/d/cae3fea57d7cf2d4

Nice. Thanks for that.

> 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.

Those are two ways of saying the same thing. If you want to use a fancier algorithm, then fine.

Then 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.

There 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.

I 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.)

Reply on news.ycombinator.com