4 ms·
The closed form solution as implemented will use floats with some fixed number of bits, right? So it cannot possible compute the numbers precisely except in a
by pfdietz 3y ago
The closed form solution as implemented will use floats with some fixed number of bits, right? So it cannot possible compute the numbers precisely except in a finite number of initial cases.
Computing the matrix power by squaring means the sizes of the integers are small until the final step, so that final step dominates the run time.
- munchler 3y agoI think you're right, and the article says "in some rare cases the method may produce incorrect result due to approximation errors".
- pfdietz 3y agoIf by "rare cases" one means "for all but a small number of cases".
- tedunangst 3y agoWhat's "small" in this case? I only have 32GB of RAM, which is only enough for a vanishingly small set of Fibonacci numbers.
- chowells 3y ago79. There are only 79 Fibonacci numbers (starting at 0, counting the 1 twice) that are exactly represented by a double-precision float. That's a lot less than 32GB of RAM.
- __rito__ 3y agoYup, I implemented all these, and only naive Python array based approach is the most practical, Python being a GC language. For all other things that I tried, I either get integer overflows (for linear algebra based implementations) or floating point errors (for the closed form).
- scythe 3y agoAll of this gets much easier if you notice that the smaller eigenvalue is less than one. So its contribution becomes exponentially smaller at higher F_i. Hence, you can just take the corresponding power of phi, multiply by some constant I forgot, and round to the nearest integer. No need for an exact formula.
- contravariant 3y agoI mean if you want to have the value as a float I reckon the closed form will suit you just fine. You can try to do it with arbitrary precision integers, but obviously the runtime can't be faster than the size of the answer, which technically makes it linear again. It can be quite fast though. I especially like Julia for this. 1) because you can just tell it to use arbitrary precision ints and 2) because you can write a power function that works for everything, floats, ints, matrices with arbitrary precision integers. Which gives one of my favourite one-liners: fib(n) = ((BigInt [1 1; 1 0])^n)[2,1] Last time I checked a manual implementation of exponentiation through squaring is just as fast as the native one. If I recall correctly the 10^9th fibonacci number is a few hundred megabytes, beyond that points things get a bit tricky.
- Someone 3y ago> If I recall correctly the 10^9th fibonacci number is a few hundred megabytes, It’s easy to prove that fib(n) < 2^n (If you need a hint: use induction), so it should be less than 10⁹ bits, or 128 megabytes. And that bound isn’t tight. A tighter one is 2log(phi) bits per step. That’s slightly less than 0.7, so that would make it less than 90 megabytes.
- contravariant 3y agoI may have remembered its size as an ASCII string.
- pfdietz 3y ago> You can try to do it with arbitrary precision integers, but obviously the runtime can't be faster than the size of the answer, which technically makes it linear again. The time will be dominated by the time to multiply integers in the final stage of the repeated squaring, which is superlinear in the number of bits. (1) (1) for fixed word size. One might instead argue it's a function of the number of words (# of bits/word size) and that the word size must eventually increase as integers get larger, asymptotically.