# How did Knuth derive A?

When interpreting keys as natural numbers we can use the following formula.

\begin{equation} h(k) = \lfloor m (kA\bmod{1}) \rfloor \end{equation}

What I am having trouble understanding is how we choose the value of A where:

\begin{equation} 0 < A < 1 \end{equation}

According to Knuth an optimal value is:

\begin{equation} A \thickapprox (\sqrt{5} - 1) / 2 = 0.6180339887... \end{equation}

So my question is how did Knuth come to this and how could I calculate an optimum value for my specific data?

• I just find it interesting that $A = 1+\phi$ ... and googling that actually brought a reference to "Knuth argues that repeated multiplication by the golden ratio will minimize gaps in the hash space, and thus it's a good choice for combining together multiple keys to form one." – Ahmed Masud Jan 6 '12 at 20:28
• If I recall correctly it's explained in one of the exercises in what sense $kA \mod 1$ are nicely spread in the unit interval. I don't have the book now to check, though. – Radu GRIGore Jan 7 '12 at 1:09
• @RaduGRIGore it's a well-known theorem that $A, 2A, \ldots$ is uniformly-distributed modulo $1$ for any irrational $A$ (theorem 6.3 of Niven's "Irrational Numbers"). Perhaps $A=1+\phi$ is the best choice in some sense. – didest Jan 7 '12 at 2:30
• There is no such thing as "more optimum"; that's like saying "more best". Either it is the optimum value or it isn't. – Jeffε Jan 7 '12 at 18:45
• It's worth pointing out that this value is also used by natural processes. Specifically, the golden angle governs the placement of petals, florets, etc. in many plants. A rotation by this angle can be applied repeatedly when placing points around a circle and the points will be evenly spaced (within a constant factor). – James King Jan 7 '12 at 20:31

## 1 Answer

See exercise 9 of section 6.4 of The Art of Computer Programming.

Any irrational $A$ would work, because $\{kA\}$ breaks up a largest gap of $\{A\}, \{2A\}, \ldots, \{(k-1)A\}$ (I use the notation $\{x\}$ for $x\mod 1$).

But if $A = \phi^{-1}$ or $A = \phi^{-2}$, it has a special property: these are the only values for which neither of the two newly created gaps is more than twice as long as the other.

• Also, the size of the smallest gap is as large as possible. – Jeffε Jan 7 '12 at 18:46