[This page is auto-generated; please prefer to read the article’s PDF Form.]
It is evident from relation (5) that the mutual ratio of the gap-lengths is itself the golden-ratio ϕ. This is an interesting and useful property of the golden-ratio.
Note that for any general real number α, although there are only two or three gap-lengths always, but the lengths need not be in a ratio (large to small) close to 1 or 2. But for α = ϕ, we found that they are always in the ratio ϕ ≈ 1.6. So, the lengths are not very disproportionate with each other.
In fact, from book [2], chapter 6.4 “Hashing”, exercise 9 we learn that — only when {α} = 1∕ϕ or 1∕ϕ2 (note that 1∕ϕ = ϕ − 1, and 1∕ϕ2 = 1 − 1∕ϕ), do we have the two smallest gap-lengths in ratio (large to small) not exceeding 2 for any N number of values. For all other α, this ratio will exceed 2 for some N.
It is this property of ϕ which makes it unique among all real numbers with regard to the “closeness” of the gap-lengths. So, if we are looking to make the distribution of {mα} in [0,1] as uniform as possible for all N, then {α} = 1∕ϕ or 1∕ϕ2 are good choices.
In Figure 1, we observe that the distribution of {mϕ} for N = 100 has good uniformity. There are no cluster of values around any point.
■
[1] Nitin Verma. Three Distance Theorem.
https://mathsanew.com/articles/three_distance_theorem.pdf
(2020).
[2] Donald E. Knuth. The Art of Computer Programming, Vol.3, Second Edition. Addison-Wesley, 1998.
Copyright © 2021 Nitin Verma. All rights reserved.