loved this article thanks !
do folks actually read knuth ? i thought his tomes were meant only for bookshelves -lol- -sarcasm-
A linear algebra trick for computing Fibonacci numbers fast
71–76 of 76 posts
Re: A linear algebra trick for computing Fibonacci numbers fast
#72It's easier to treat these as linear difference equations with constant coefficients and use the ansatz of λ^{n}. This is morally the same thing but without the need for matrix manipulation. Knuth, Oren and Patashnik's Concrete Mathematics is full of these and is required reading for discrete math.
I came here to say the same: difference equations, z-transform, recurrence relations, are (or used to be) standard undergrad eng curriculum (typically via some required Signals & Systems course). Maybe not so popular in the CS world though?
Beautiful expo on the subject: https://eee.guc.edu.eg/Courses/Communications/COMM401%20Sign... (Chapter 10, etc.)
Re: A linear algebra trick for computing Fibonacci numbers fast
#73Earlier quoted context omitted.
Python has arbitrary precision integers, so you could do it without running into overflows. Although if implementing floating point based technique, you may want to use np.float128 to handle values upto 10^4932.
> you may want to use np.float128 to handle values upto 10^4932. I'm not sure the maximum value matters, since I think it only actually gives you 33 decimal digits precision and the 1500th number has over 300 digits. Although it looks like you'd need to be more careful with it too: https://numpy.org/doc/stable/user/basics.types.html > np.float96 and np.float128 are provided for users who want specific padding. In spi…
My bad. I should have looked into the docs. Thanks for pointing out!
Re: A linear algebra trick for computing Fibonacci numbers fast
#74loved this article thanks ! do folks actually read knuth ? i thought his tomes were meant only for bookshelves -lol- -sarcasm-
Thank you (author here).
I don't read TAOCP. I have read first few chapters of volume-1 so I am familiar with the notation and some MIX syntax.
But while writing this article, I just opened up specific topics, such as computing Fibonacci numbers in volume-1, or evaluating powers in volume-2 and I managed to understand it. Sometimes you may find back references, such as when discussing Fibonacci numbers, he references Euclid's algorithm and you may have to go back and check it out, or ignore it (depends on the context). So I believe you don't necessarily need to read from cover to the end; you can browse it based on your interest.
Re: A linear algebra trick for computing Fibonacci numbers fast
#75The 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.
I 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 writ…
> 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.
Re: A linear algebra trick for computing Fibonacci numbers fast
#76It's easier to treat these as linear difference equations with constant coefficients and use the ansatz of λ^{n}. This is morally the same thing but without the need for matrix manipulation. Knuth, Oren and Patashnik's Concrete Mathematics is full of these and is required reading for discrete math.
Note that “Oren and Patashnik” is one person named Oren Patashnik.
Thanks! The correct authors are Graham, Knuth, and Patashnik.