An integer formula for Fibonacci numbers
paulhankin.github.io
paulhankin.github.io
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
With yours, both make interesting comparison of how similar problem is solved in different languages.
def fib(n):
return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1)
fib(0) = 0
fib(1) = 1
fib(2) = 2
fib(3) = 3
fib(4) = 5
etc.
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.)
Fib(0) = 1
Fib(1) = 1
Fib(n) = Fib(n−1) + Fib(n−2)
X = 10**3
print X**16//(X*X-X-1)
# 1001002003005008013021034055089144233377610
fib = 0 : 1 : zipWith (+) fib (tail fib)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:
(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.
Fn=(1+√5)^n−(1−√5)^n\2^n√5
This deravation is pretty accessable and if you want to show off in code tests :)
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.
This is a classic programming question, and it's refreshing to see a closed form solution.
[1]:https://scottsievert.com/blog/2015/01/31/the-mysterious-eige...
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)
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.
(It is not fastest because the trivial binary approach doesn't product optimal addition chains. See https://en.wikipedia.org/wiki/Addition_chain or (dense writing, as is normal in HAKMEM) http://www.inwap.com/pdp10/hbaker/hakmem/recurrence.html)
Also, there is a very simple method for implementing "isFib":
isFib(n) := isSquare(5n^2+4) or isSquare(5n^2-4) (4 << n*(3+n))
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.
Fibonacci(n) = (Φ^n - (1-Φ)^n) / √5
(Where Φ = (1 + √5) / 2)See https://math.temple.edu/~reich/Fib/fibo.html for more on the Fibonacci sequence and the golden mean.
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)".
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.
More broadly code lacking structure, hard to compose, or improperly not composed of smaller components.
The idea was mapping flow looked like a tangled mess.
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
This all sounds cool until someone actually hands you "Mel's" code: http://www.pbm.com/~lindahl/mel.html
PS: Beginners or Evil people, would also get into horrid messes by trying to get something that sort of works into something that almost worked.
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?
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.
[1] found an instance here: http://austinrochford.com/posts/2013-11-01-generating-functi...
> 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.
I guess I don't know as much math as I thought.
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)=ΣnFib(n+1)x^(n+2)+ΣnFib(n)x^(n+2)
to this one:
F(x)−x−1=x(F(x)−1)+x2F(x)
I haven't managed to figure it out and have a couple of colleagues that haven't been able to work it out as well.