87 points by _Microft 2 days ago | 16 comments | View on ycombinator
sph 2 days ago |
mbf1 2 days ago |
_Microft 2 days ago |
https://www.johndcook.com/blog/2023/08/12/fibonacci-lattice/
Tepix 2 days ago |
rmunn 2 days ago |
But the golden ratio is defined as the number a/b that is also equal to (a+b)/a. Now (a+b)/a = a/a + b/a. And what is b/a but 1/(a/b). So the golden ratio, phi, can be written as phi = 1 + 1/phi. Now substitute (1 + 1/phi) for the phi in that right-hand side and you get phi = 1 + 1/(1 + 1/phi). Substitute again and you continue to get (1 + 1/phi) terms continuing onwards. Which means that the continued fraction of phi is just [1, 1, 1, 1, 1, 1 ...] forever.
Since there is no number higher than 1 in that continued fraction, there is no point at which you can take the approximation and know that it's better than taking the approximation somewhere else, unlike pi where you can know that 355/113 is very very close. There is no rational fraction that is a better approximation of the actual value than what you would have gotten if you went another step or two down the chain. (Proportionally speaking, of course: naturally you'll get more decimal digits of correctness the longer you go, but at no point will the proportions be better).
So that's why the golden ratio is the most irrational number. Any other irrational number has at least one point where there's a 2 (or higher) in the continued fraction, meaning there is some place you could stop the continued fraction and get a better approximation than stopping elsewhere. There is some rational fraction that is a better approximation to the actual value than other rational fractions. But the golden ratio's continued-fraction representation is just 1s, forever. And that means there is no place you can stop and say "this spot is a better approximation than the others". It's the most irrational number.
eggnog92 2 days ago |
Jacky101 2 days ago |
https://probablydance.com/2018/06/16/fibonacci-hashing-the-o...
The graph of the distribution is indeed very similar to the LEDs in this article: https://book.huihoo.com/data-structures-and-algorithms-with-...
So if you find yourself doing:
Consider introducing Fibonacci hashing. And the reason this works, and provides uniform distribution is this: https://en.wikipedia.org/wiki/Equidistribution_theorem