logoalt Hacker News

Why Fibonacci?

39 points • by _Microft • today at 5:35 AM • 5 comments • view on HN

Comments

_Microft • today at 10:09 AM

If you are curious about a three-dimensional case of distributing points (relatively) evenly, then John Cook has something on that for points on a sphere. And it's also using a Fibonacci pattern.

https://www.johndcook.com/blog/2023/08/12/fibonacci-lattice/

➕ show 1 reply
sph • today at 7:42 AM

I just learned about Fibonacci hashing, where you multiply a hash function by a certain factor derived from the golden ratio, which gives you better distribution than a bare integer modulo.

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:

    bucket = hash % total_buckets;
Consider introducing Fibonacci hashing. And the reason this works, and provides uniform distribution is this: https://en.wikipedia.org/wiki/Equidistribution_theorem
➕ show 1 reply
mbf1 • today at 6:07 AM

I noticed in step 5 of this that you get spirals at Fibonacci numbers like 55 and 89 (which are 34 apart). However, if you pick 72 which is half way between the spirals, you see something interesting happen.

Jacky101 • today at 6:56 AM

[dead]