Why Fibonacci?

(evilgeniuslabs.org)

55 points | by _Microft 8 hours ago ago

9 comments

  • sph 6 hours ago ago

    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
    • noduerme 3 hours ago ago

      Is this used for smoothing any other kinds of outputs that you know of? Like, say, removing noise from big data tables you're using for symbolic regression? I've never come across this before but it seems like it's got a lot of potential compared to other methods.

  • Tepix 19 minutes ago ago

    Neat! The final animation shown might be a good match for the cheap e-badges that have been reverse engineered with their round 240x240 or 320x320 displays (SuperBand, Fitpro, dg01, dg02, BJ-1, ...)

  • mbf1 7 hours ago ago

    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.

  • _Microft 3 hours ago ago

    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/

    • stefanka 3 hours ago ago

      Can this be extended to n-dimensions or a n-torus?

  • rmunn 2 hours ago ago

    I think it was the Numberphile video on the Golden Ratio that taught me this fun fact: the Golden Ratio is the most irrational number possible. If you write out an irrational number as a continued fraction (x + 1/(y + 1/(z + 1/...))), or [x, y, z] in shorthand notation, then anywhere there's a large number for x, y, or z, that's a place where you can produce a good approximation. For example, pi is 3 + the continued fraction [7, 15, 1, 292, 1, ...]. The number 15 means there's a pretty large denominator there, so a small value added to 3+1/7, meaning that 22/7 is a halfway decent approximation of pi. But that 292 means that the fraction at that point is 3 + 1/(7 + 1/(15 + 1/(1 + 1/(292 + ...)))). Now 1/(292 + small amount) is a very small number, so if you drop that off, then the value you get won't be very far off from pi at all. So you can round that to 3 + 1/(7 + 1/(15 + 1/(1 + 0))) which is equal to 355/113 — and it turns out that that's quite a good approximation of pi for practical everyday uses, as it's correct to six decimal points.

    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.

    • gjm11 4 minutes ago ago

      Fun fact: this is why the musical interval called a tritone[1] sounds so dissonant that it's been called "diabolus in musica", "the devil in music"[2].

      In equal temperament[3] you get this interval from two notes whose frequencies differ by a factor of the square root of 2. And this also has a continued fraction whose coefficients are very small: [1,2,2,2,...], so it also is very badly approximated by rational numbers.

      And the musical intervals that sound "clean" and consonant are exactly those that are very close to simple rational numbers. Why? No one knows for certain but the following seems to be a big part of the answer[4]: most of the instruments we use in "Western" music involve some basically-one-dimensional thing sustaining vibrations: either a string (violin, piano, guitar, ...) or a long thin tract of air (oboe, trumpet, organ, voice, ...). The modes of vibration such a thing can support have frequencies lying in arithmetic progression: f, 2f, 3f, etc. or some subset thereof. So the sound of any note you play with such a thing can be thought of as a combination of pure sinusoidal tones at those frequencies.

      Now, if you have people listen to two-note chords where the individual notes are pure sinusoids then they don't strongly prefer simple-rational-number frequency ratios. Instead, what happens is that if the frequencies are very close but not so close that they sound like a single note, the "beating" effects become unpleasant, and that's where a sense of dissonance comes from.

      And if instead you combine two notes each of which is built out of lots of sinusoids at frequencies f1, 2.f1, 3.f1, etc., and f2, 2.f2, 3.f2, etc., then you get dissonance when two of the constituent sinusoids are close-but-not-close-enough. And if the ratio between f1 and f2 is a simple rational number then all the "close" things line up exactly[5] so the level of dissonance is low; if it's very close to a simple rational number then they line up almost exactly which is almost as good; but if not, then there are pairs that come close-but-not-close-enough.

      So very-irrational ratios -> clashing harmonics -> dissonance, so a sqrt(2) frequency ratio sounds dissonant, so a tritone sounds dissonant. Diabolus in musica!

      [1] or augmented fourth, or diminished fifth; C to F#, etc; the interval at the start of "Maria" from West Side Story and all over Britten's War Requiem

      [2] Claims that the use of this interval was forbidden by the Church, etc., are bullshit, though.

      [3] Where you divide an octave into twelve exactly equal semitones. This has been the usual arrangement in "Western" music for quite some time, but it's not the only thing you can do. However, what I say about tritones is still approximately true in other temperaments.

      [4] William Sethares's book Tuning, Timbre, Spectrum, Scale gives a very nice account of this.

      [5] If you make this mathematically precise then you get a theorem of the form "two unequal rational numbers can't be too close together given the size of their denominators", which is what you use to e.g. prove that e, the base of natural logarithms, is not a rational number, because the well-known infinite series for it gives you very-good-but-not-exact rational approximations.

    • NervousDendrite an hour ago ago

      Excellent write-up, I was wondering whether the properties explored in the post could just apply to any irrational number.