Wie hat Knuth A abgeleitet?

9

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

h(k)=m(kAmod1)

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

0<A<1

Ein optimaler Wert ist nach Knuth:

A(51)/2=0.6180339887...

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

ChaosPandion
quelle
3
Ich finde es einfach interessant, dass ... und Googeln, das tatsächlich einen Verweis auf "Knuth" enthält, argumentiert, dass wiederholte Multiplikation mit dem goldenen Schnitt Lücken im Hash-Raum minimiert und daher eine gute Wahl für die Kombination ist mehrere Schlüssel, um einen zu bilden. " A=1+ϕ
Ahmed Masud
1
Wenn ich mich richtig erinnere, wird in einer der Übungen erklärt, in welchem ​​Sinne im Einheitsintervall gut verteilt sind. Ich habe das Buch jetzt allerdings nicht zum Überprüfen. kAmod1
Radu GRIGore
1
@RaduGRIGore Es ist ein bekannter Satz, dass Modulo für jedes irrationale gleichmäßig verteilt ist (Satz 6.3 von Nivens "Irrational Numbers"). Vielleicht ist in gewissem Sinne die beste Wahl. A,2A,1AA=1+ϕ
Didest
2
Es gibt kein "optimaleres"; das ist wie "mehr am besten" zu sagen. Entweder ist es der optimale Wert oder nicht.
Jeffs
2
Es sei darauf hingewiesen, dass dieser Wert auch von natürlichen Prozessen genutzt wird. Insbesondere regelt der goldene Winkel die Platzierung von Blütenblättern, Blütchen usw. in vielen Pflanzen. Eine Drehung um diesen Winkel kann wiederholt angewendet werden, wenn Punkte um einen Kreis platziert werden, und die Punkte werden gleichmäßig verteilt (innerhalb eines konstanten Faktors).
James King

Antworten:

19

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},,{(k1)A}{x}xmod1

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=ϕ1A=ϕ2

tatest
quelle
7
Auch die Größe der kleinsten Lücke ist so groß wie möglich.
Jeffs