Wie hat Knuth A abgeleitet?

Bei der Interpretation von Schlüsseln als natürliche Zahlen können wir die folgende Formel verwenden.

Was ich nicht verstehen kann, ist, wie wir den Wert von A wählen, wo:

Ein optimaler Wert ist nach Knuth:

Meine Frage ist also, wie Knuth dazu gekommen ist und wie ich einen optimalen Wert für meine spezifischen Daten berechnen kann.

Siehe Übung 9 von Abschnitt 6.4 der Kunst der Computerprogrammierung .

Jedes irrationale würde funktionieren, weil eine größte Lücke von aufbricht (ich verwende die Notation für ).$A$$\{kA\}$$\{A\}, \{2A\}, \ldots, \{(k-1)A\}$$\{x\}$$x\mod 1$

Wenn jedoch oder , hat dies eine besondere Eigenschaft: Dies sind die einzigen Werte, für die keine der beiden neu erstellten Lücken mehr als doppelt so lang ist wie die andere.$A = \phi^{-1}$$A = \phi^{-2}$