[HN Gopher] The Fibonacci Matrix
___________________________________________________________________
The Fibonacci Matrix
Author : ianthehenry
Score : 111 points
Date : 2023-07-31 13:14 UTC (9 hours ago)
(HTM) web link (ianthehenry.com)
(TXT) w3m dump (ianthehenry.com)
| Rietty wrote:
| [dead]
| dpflan wrote:
| Excellent post!
| FrustratedMonky wrote:
| Concur. This was excellent.
| hammock wrote:
| 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:_
| 8 / 41 = 0.1951219 (8 + 41 = 49) / 8 = 6.125 (49 + 8
| = 57) / 49 = 1.16326531 (57 + 49 = 106) / 57 = 1.85964912
| (106 + 57 = 163) / 106 = 1.53773585
|
| _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. 8
| 10 1.25 18 1.8 28 1.555555556 46 1.642857143
| 74 1.608695652 120 1.621621622 194 1.616666667
| 314 1.618556701
| ianthehenry wrote:
| 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).
| hammock wrote:
| It converges because there is just one error then you do the
| operation correctly after that.
|
| Your sequence is 8 41 49 57
| 106 163
|
| What you are looking for is 8 41
| 49 90 139 229
| ianthehenry wrote:
| 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.
| hammock wrote:
| I see now and also the author acknowledges above. Thanks
| for clarifying
| ducttapecrown wrote:
| 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).
| supernewton wrote:
| > 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).
|
| Well, almost. You need to multiply by a factor of 1/sqrt(5)
| before rounding.
| ironborn123 wrote:
| note that f_n = (a^n + b^n) / sqrt(5) ~ a^n / sqrt(5)
|
| the denominator is important.
|
| also another interesting relation is a^n ~ f_(n+1) + f_(n-1) =
| f_(n+2) - f_(n-2)
| Strilanc wrote:
| Awesome.
|
| 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...).
| ianthehenry wrote:
| That's such a good idea! Sadly I am at work right now so I
| can't hack on it for a while, but I love it
| alanbernstein wrote:
| I like your interactive animation, would you mind briefly
| describing how you did the canvas pixel art?
| ianthehenry wrote:
| 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.
| rahkiin wrote:
| 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.
|
| Nice quip at the end as well :)
| inasio wrote:
| It reminded me Cleve Moler's (Matlab creator) awesome paper: 19
| dubious ways to exponentiate a matrix [1]:
|
| [1]: https://www.math.purdue.edu/~yipn/543/matrixExp19-I.pdf
| danaugrs wrote:
| Very cool! Love the visualizations.
| glonq wrote:
| This was written to be surprisingly accessible to somebody who
| hasn't touched a college math textbook in two or three decades.
| Well done!
___________________________________________________________________
(page generated 2023-07-31 23:02 UTC)