<p>See exercise 9 of section 6.4 of <a href="https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming" rel="nofollow"><em>The Art of Computer Programming</em></a>.</p>

<p>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$).</p>

<p>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.</p>

CC BY-SA 3.0
2012-01-07T18:46:19.550Z
Also, the size of the smallest gap is as large as possible.
Jeffε
CC BY-SA 3.0
2012-01-07T02:47:47.513Z
2015-01-08T08:09:41.883Z
2015-01-08T08:09:41.883Z
didest
<p>When interpreting keys as natural numbers we can use the following formula.</p>

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

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

<p>\begin{equation}
0 &lt; A &lt; 1
\end{equation}</p>

<p>According to Knuth an optimal value is:</p>

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

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

CC BY-SA 3.0
2012-01-06T20:28:34.817Z
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
CC BY-SA 3.0
2012-01-07T01:09:51.750Z
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
CC BY-SA 3.0
2012-01-07T02:30:24.187Z
@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
CC BY-SA 3.0
2012-01-07T18:45:30.190Z
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ε
CC BY-SA 3.0
2012-01-07T19:02:40.177Z
@JɛﬀE - I truly appreciate your insightful comment.
ChaosPandion
CC BY-SA 3.0
2012-01-07T20:31:08.217Z
It's worth pointing out that this value is also used by natural processes.  Specifically, the [golden angle](http://en.wikipedia.org/wiki/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
<hash-function>
How did Knuth derive A?
ChaosPandion
# How did Knuth derive A?

(Asked by: username_0 on 2012-01-06)

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?

**Tags:** hash-function

> **Comments:**
> **username_1**: 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."  
> **username_2**: 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.  
> **username_3**: @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.  
> **username_4**: There is no such thing as "more optimum"; that's like saying "more best".  Either it is the optimum value or it isn't.  
> **username_0**: @JɛﬀE - I truly appreciate your insightful comment.  
> **username_5**: It's worth pointing out that this value is also used by natural processes.  Specifically, the [golden angle](http://en.wikipedia.org/wiki/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).  

---

## 1 answers

### Answer by username_3 on 2012-01-07. Score: 20 | Accepted answer

See exercise 9 of section 6.4 of [*The Art of Computer Programming*](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_4**: Also, the size of the smallest gap is as large as possible.  

---

