Something I noticed in the plot where you can add points is that it's not actually using the continuous version of the transformation to interpolate the paths. It looks like the points are being linearly interpolated between integer powers of the transition matrix. Once you've got the eigenvalues and eigenvectors, you can easily raise the transition matrix to fractional powers to get things like square roots and show halfway points. I think if you interpolated that way then you'd get smooth spirals towards the golden ratio line, instead of bounces (keeping in mind that because one of the eigenvalues is negative you'd end up with complex numbers requiring a projection down from 4d to 2d...).
Of course you can also just have a good approximation of phi and multiply your coordinates by arbitrary powers of that. That will just slide you along the diagonal, but it becomes very accurate very quickly.
This was the content of the final lecture of a linear algebra class I took. It was magical to learn about the explicit formula for Fibonacci numbers found via eigendecomposition.
One funny trick that brought some realism to the lecture: If a and b are the golden ratio and its conjugate, then f_n = a^n + b^n. But since |b| < 1, you can just do f_n = nearest_integer(a^n).
Loved the reference to ‘dynamic programming’ in university. This is exactly what happened in mine and love to see the normal non-recursive version is just nicer.
There are a couple of errors I noticed. When the author says:
Even if we start with two numbers that are completely unrelated in the Fibonacci sequence – say, 8 and 41 – the simple way that we pick the next number of the Fibonacci sequence will cause us to approximate the golden ratio after only a few iterations:
Why is that? Well, because of the definition of the golden ratio.
He mis-adds in the third step 8+41 ought to be 41+49..
But that's not all. He says "if we start with [any] two numbers...in the Fibonacci sequence" but in fact you can start with ANY two numbers WHETHER OR NOT they are fibonacci numbers.. and perform the Fibonacci operation and divide adjacent numbers and it will converge to the golden ratio. E.g.
The example is showing current=8 previous=41, not current=41 previous=8. I think I did the math right from the those (weird) initial conditions, but maybe not. It converges either way!
Good call on the wording there, though -- changed it from "completely unrelated in the Fibonacci sequence" to "completely unrelated to the Fibonacci sequence" (41 is not a Fibonacci number).
Yeah, if you swap the initial conditions, you get a different sequence of values. You’re starting with 8 41, but the sequence in the article starts with 41 8.
The "how to fibonacci" table is missing one other fun and clever way that I want to share -- using a field extension.
Using the Binet closed form for Fibonacci with floating point numbers is problematic because of finite precision. Naive exponentiations of the golden ratio are not accurate. Part of the problem is the infinite precision needed to deal with sqrt(5).
One way to deal with that is to represent numbers in the numerator or denominator as (a + b √5) with a and b as integers. Whenever the √5 gets multiplied you separate it out as 5.
This is way is not faster. One ends up with the logarithmic complexity of exponentiation by squaring. Nonetheless its quite fun and accurate.
Yeah, it's really pretty simple -- there's a CSS rule `image-rendering: pixelated;` which sets it to use nearest-neighbor resampling. Then you render a canvas that's half the width of your screen and scale it up.
You kinda have to use WebGL for this to look good, though, because the vanilla 2D canvas has no way to disable anti-aliasing, so you can't really get those crisp pixely lines.
Something I noticed in the plot where you can add points is that it's not actually using the continuous version of the transformation to interpolate the paths. It looks like the points are being linearly interpolated between integer powers of the transition matrix. Once you've got the eigenvalues and eigenvectors, you can easily raise the transition matrix to fractional powers to get things like square roots and show halfway points. I think if you interpolated that way then you'd get smooth spirals towards the golden ratio line, instead of bounces (keeping in mind that because one of the eigenvalues is negative you'd end up with complex numbers requiring a projection down from 4d to 2d...).