Comment Knuth a-t-il dérivé A?

9

Lorsque nous interprétons les clés comme des nombres naturels, nous pouvons utiliser la formule suivante.

h(k)=m(kAmod1)

Ce que j'ai du mal à comprendre, c'est comment nous choisissons la valeur de A où:

0<A<1

Selon Knuth, une valeur optimale est:

A(51)/2=0.6180339887...

Donc, ma question est de savoir comment Knuth est arrivé à cela et comment pourrais-je calculer une valeur optimale pour mes données spécifiques?

ChaosPandion
la source
3
Je trouve juste intéressant que A=1+ϕ ... et googler qui a en fait fait référence à "Knuth fait valoir que la multiplication répétée par le nombre d'or minimisera les écarts dans l'espace de hachage, et c'est donc un bon choix pour combiner ensemble plusieurs clés pour en former un. "
Ahmed Masud
1
Si je me souviens bien, cela est expliqué dans l'un des exercices dans quel sens est bien réparti dans l'intervalle unitaire. Je n'ai pas le livre à vérifier maintenant. kAmod1
Radu GRIGore
1
@RaduGRIGore c'est un théorème bien connu que est un modulo uniformément distribué pour tout irrationnel (théorème 6.3 des "Nombres irrationnels" de Niven). Peut-être que est le meilleur choix dans un certain sens. A,2A,1AA=1+ϕ
didest
2
Il n'y a pas de "plus optimal"; c'est comme dire "plus mieux". Soit c'est la valeur optimale, soit ce n'est pas le cas.
Jeffε
2
Il convient de souligner que cette valeur est également utilisée par les processus naturels. Plus précisément, l' angle doré régit le placement des pétales, des fleurons, etc. dans de nombreuses plantes. Une rotation de cet angle peut être appliquée à plusieurs reprises lorsque vous placez des points autour d'un cercle et les points seront régulièrement espacés (dans un facteur constant).
James King

Réponses:

19

Voir l'exercice 9 de la section 6.4 de L'art de la programmation informatique .

Tout irrationnel fonctionnerait, car brise un plus grand espace de (j'utilise la notation pour ).A{kA}{A},{2A},,{(k1)A}{x}xmod1

Mais si ou , il a une propriété spéciale: ce sont les seules valeurs pour lesquelles aucun des deux espaces nouvellement créés n'est plus de deux fois plus long que le autre.A=ϕ1A=ϕ2

didest
la source
7
En outre, la taille du plus petit espace est aussi grande que possible.
Jeffε