Hacker News
Why Fibonacci?
sph
|next
[-]
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
mbf1
|next
|previous
[-]
_Microft
|next
|previous
[-]
https://www.johndcook.com/blog/2023/08/12/fibonacci-lattice/
Tepix
|next
|previous
[-]
rmunn
|next
|previous
[-]
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
|root
|parent
|next
[-]
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.
rmunn
|root
|parent
|next
[-]
amavect
|root
|parent
|previous
[-]
7/5 does show up in the continued fraction, and I consider it consonant. 13/8 approximates the golden ratio, and I also consider it consonant, but with an acquired microtonal taste.
NervousDendrite
|root
|parent
|previous
[-]
empath75
|root
|parent
[-]
This is more or less about the properties of rational approximations of badly approximable numbers in general, which is a much larger class than phi, but not “all irrational numbers”
What is interesting about phi in particular is that phi is badly approximable at even the smallest truncations, so it produces a good spacing immediately. You could take _any_ irrational number, and replace it’s usual continued fraction representation after a certain point with all 1s, like phi, and with enough seeds, the placement would start to look like phi’s.
Even something like 1/4th, if you just tweak it a _little_ bit can start having this property after millions or billions of seeds.