Nice. When I was a teenage self-taught programmer, an article like this one, but about the superiority of quicksort to insertion sort, was the trigger that got me to understand that thinking mathematically about algorithms could lead us to a kind of understanding that transcended mere coding (although I couldn't have put it in those words at that time). It was quite an epiphany.
I can imagine, today, a young enthusiast having learned Python and maybe done a few Project Euler exercises, stumbling upon that post and being amazed that you could generate Fibonacci numbers that way, and thinking that maybe there is something interesting about that "generating functions" thing.
But there should be two values at the beginning that evaluate to 1. (Whether it's fib(0) and fib(1), vs. fib(1) and fib(2) is just a matter of convention. But there should definitely be two of them.)
I never really thought about evaluating a z-transform at a particular value, so I tied together some of the various solutions with derivations and greater generality here:
He says that this is an inefficient way to generate the nth Fibonacci number, but since it actually gives you the first n Fibonacci numbers, thats not the fairest comparison. (Especially since the fastest methods for finding the nth Fibonacci number don't generate all the intermediates.)
Just for curiosity sake, how does using this formula to generate all of the first n Fibonacci numbers compare to other ways of doing that?
(You get all n with the same formula by replacing the mod 2^(n+1) (or reading the last n+1 bits) by splitting the whole integer that is generated into n+1 bit chunks.
That's given early in the article, but requires arbitrary precision arithmetic:
Another method is to find a closed form for the solution of the recurrence relation. This leads to the real-valued formula: Fib(n)=(ϕn+1−ψn+1)/5‾√)
where ϕ=(1+5‾√)/2 and ψ=(1−5‾√)/2. The practical flaw in this method is that it requires arbitrary precision real-valued arithmetic, but it works for small n.
If you add a "round to integer" step at the end, it doesn't require arbitrary precision arithmetic. Careful numerical analysis can tell you how many digits of precision you need to compute fib(n).
I would guess the end result would be similar to that of this method (2n bits being more than sufficient), the difference being that this method puts all the digits before the decimal point.
Also, for large n, you may be able to assume ψ = 0 to speed up computations (given ψ < n, its nth power will get vanishingly small)
But the matrix method is the easiest fast method one can write and prove robust.
Most fast methods for computing fib(n) come down to some variation of repeated squaring, so the time is dominated by the last multiplication (since the number of digits is doubling each time).
At first glance, the given integer formula is worse regarding arbitrary precision. The first bracket term is
(4 << n*(3+n))
That is shifting 4 by n squared digits to the left, requiring more than n^2 binary digits.
I think calling this an integer formula is misleading, since in computing algorithms, by integers we normally understand the basic integer supported by an ALU. This formula, while dealing with integers in the mathematical sense, deals with arbitrary precision (or bignum, or whatever you call it) in the computing sense.
I'm the author of the blog post. You're right, it requires n^2 binary digits (and I mention this at the end of the article). The formula isn't, and isn't meant to be, a good way to find Fibonacci numbers -- it's more of a fun curiosity.
That it's the fastest is pretty surprising to me. Both Binet and matrix multiplication require exponentiation to n, which can be done in O(log n) multiplications (not n-1) using a clever recursion (and indeed numpy uses it). 2x2 matrices aren't exactly the hardest to multiply either, but I figured that the floating point operations with the Binet formula would enough baggage that would make it slower than the matrix method. Edit: I just saw Someone's comment - I guess that explains it.
No, it doesn't, if I understand the OPs claim correctly.
I agree with you that, for large enough n, using O(n) steps in the recursion will be slower than doing O(log n) matrix multiplication steps. The addition chain improves on the binary approach for some values of n, but I don't think it can go below O(log n) because the binary method is fastest for all n that are powers of two (disclaimer: I know almost nothing of addition chains besides what I learned from TAOCP).
And of course, finding the fastest addition chain doesn't come cheaply, either, if P != NP.
Hm, maybe I understand the OP's claim: if you want to generate the first n items in the series, the recursive formula will be hard to beat. Even then, it may not be fastest on modern CPUs. https://oeis.org/A000045 gives
F(n + 12) = 18F(n + 6) - F(n)
So, six completely independent threads can each compute a sixth of the sequence. Doing that may be faster than trying to paralllelize the bignum additions.
I like the matrix math one mentioned in the post, although I implemented the matrix arithmetic by hand.
That provides an opportunity to discuss the optimization involved in performing integer exponentiation, so you aren’t depriving an interviewer of an opportunity to have a productive conversation about programming.
Mathematically they might be the same, but they reduce to different problems in computer science. The OP uses algorithmic approaches, but yours requires finite-precision root solvers (for the calculation of \Phi ) and some numerical analysis to determine how many bits of \sqrt(5) are needed to be correct to yield a calculation of Fibonacci(n) which is correct to the nearest integer.
Otherwise, I'd point out that any result where you ultimately need to use Fibonacci(n) as an actual integer, you can't represent it as an algebraic combination of "sqrt(5)".
No joke! See this thread: https://news.ycombinator.com/item?id=11561336 for some real-life implementations of this technique. Since the Fibonacci numbers are integers, at the end of your computation you'll get a number like "a + 0 sqrt(5)". Then you can just take the "a" part.
When computing, you can ignore the second term, and just round the result to nearest integer. At for n larger than 2, or so, that should simplify calculations.
Edit: I forgot to check if there were other responses already. Oops! Never mind. Also, in addition to being late, I was also wrong (or, at best, partially wrong)
Doesn't it usually at least connotate having large amounts of code, often repetitive code? Especially code that should be split into smaller functions?
I thought that was the case, but I would not be surprised that it is also used more broadly
It's generally the other end, where there is 'not enough' code. Early systems needed to be like this because there was very little memory for your code and people would often do things use calculated jumps based on some register value. Not to mention the joys of self modifying code.
My recollection is that the closed formula (with phi) is derived from the generating function as well, though the derivation was nigh miraculous when I saw it done.
It's not miraculous at all, and doesn't need to involve generating functions :-)
Consider all sequences f(n) that fit the constraint f(n) + f(n+1) = f(n+2), with arbitrary initial values. Such sequences form a vector space, because adding them together or multiplying by a constant doesn't break the constraint. That vector space is two-dimensional, because the two initial values determine the rest of the sequence. Now we just need to find two different sequences that form a basis of that space. All other sequences can be expressed as linear combinations of these two.
How do we find the two basis sequences? Let's make a lucky guess that they are geometric progressions with some constant c. Then we have c^n + c^(n+1) = c^(n+2), or equivalently 1 + c = c^2. That equation has two solutions, phi (the golden ratio, about 1.618) and psi = -1/phi.
Going back to the original problem, we need to express the usual Fibonacci sequence (which starts with 1,1) as a linear combination of the sequences phi^n and psi^n. We just need to match the two initial values by picking the right coefficients, which turn out to be 1/sqrt(5) and -1/sqrt(5), giving you the desired closed form formula.
The above approach generalizes to any recurrence of the form a * f(n) + b * f(n+1) + c * f(n+2) + ... = f(n+k). All such sequences will form a k-dimensional vector space, and you can find k different geometric progressions by solving a polynomial equation of degree k which has k roots. All other solutions will be linear combinations of these geometric progressions. (There will be complications if some roots coincide, but it can be worked out.)
To me the whole chain of reasoning feels very natural and almost inevitable. If I didn't know anything about Fibonacci numbers but had a good grasp of popular math, that's how I would approach the problem right away. Does that make sense?
It does- I remember enough from Linear Algebra that vector spaces aren't completely foreign, which helps a lot.
I think the generating-function method[1] is a case of pulling out a powertool (generating functions) to prove a simple thing to demonstrate the power of the tool, whereas your explanation takes the direct route and connects more of the threads about why it's true.
> Multiplying by x^(n+2) and summing over all n, we get
Is n the iterating variable, or the domain? What are the possible values of n? Wouldn't "all" values (whichever set that may be) give an infinite sum? I thought that infinite expressions did not obey the same laws as finite ones, and couldn't be generally used with algebraic transformations.
Disclaimer: I have studied these functions a long, long time ago. I barely remember anything.
In that particular point in the article, n is both. It is a natural number that is the domain of Fib, and the iterating variable of the generating function. As you've noticed, the sum is indeed infinite - this does not matter, however, as at no point is the actual sum of a generating function series important - the whole series mechanism is just a nice conduit to reason about the coefficients (subsequent values of Fib, in this case) using more familiar and developed mathematics for infinite series (divergent or not).
I remember being fascinated by generating functions in college. I viewed them as sort of a beautiful hack in how to tie various combinatorial structures to the more ordinary algebraic operations. This mini-field is called enumerative combinatorics. The only part of discrete mathematics that I've actually enjoyed :)
ΣnFib(n+2)x^(n+2) is F(x)−x−1 because it's an infinite series of powers of x, except since it's x^(n+2) then x^1 (x) and x^0 (1) never appear, so you need to subtract them from F(x) which is ΣnFib(n)x^n. I hope that's clear and explains the rest.
The Lucas numbers are more interesting. Instead of starting with 1, 1, which is kind of arbitrary, start with 2, 1. The resulting sequence is exactly round(phi^n). Which is a much stronger link to the golden ratio. And is found just as often in nature.
It's nice to see something about the fibo numbers that has some real math in it, as opposed to the articles that make it big in proggit everyday that functional programming fanboys think are cool but that really discredit FP in the eyes of everybody else.
I can imagine, today, a young enthusiast having learned Python and maybe done a few Project Euler exercises, stumbling upon that post and being amazed that you could generate Fibonacci numbers that way, and thinking that maybe there is something interesting about that "generating functions" thing.
If that's you reading this, it's dangerous to go alone. Take this: https://www.math.upenn.edu/~wilf/DownldGF.html