Como Knuth obteve A?

Ao interpretar teclas como números naturais, podemos usar a seguinte fórmula.

h (k) = ⌊ m (k A mod 1) ⌋

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

O que estou tendo problemas para entender é como escolhemos o valor de A onde:

0 < A < 1

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

De acordo com Knuth, um valor ideal é:

A \approx (\sqrt{5} - 1) / 2 = 0.6180339887...

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

Portanto, minha pergunta é como Knuth chegou a isso e como calcular um valor ideal para meus dados específicos?

hash-function ChaosPandion
fonte

Apenas acho interessante que ... e Google que realmente trouxeram uma referência a "Knuth argumenta que a multiplicação repetida pela proporção áurea minimizará as lacunas no espaço de hash e, portanto, é uma boa opção para combinar várias chaves para formar uma ".

A = 1 + ϕ

$A = 1+\phi$

Ahmed Masud

Se bem me lembro, é explicado em um dos exercícios em que sentido está bem distribuído no intervalo da unidade. Eu não tenho o livro agora para verificar, no entanto.

k A \mod 1

$kA \mod 1$

Radu Grigore

@RaduGRIGore, é um teorema bem conhecido que é um módulo uniformemente distribuído para qualquer irracional (teorema 6.3 dos "Números irracionais" de Niven). Talvez seja a melhor escolha em algum sentido.

A, 2 A, \dots

$A, 2A, \ldots$

1

$1$

A

$A$

A = 1 + ϕ

$A=1+\phi$

didest

Não existe algo como "mais ideal"; é como dizer "mais melhor". Ou é o valor ideal ou não é.

Jeffε

Vale ressaltar que esse valor também é usado por processos naturais. Especificamente, o ângulo de ouro governa a colocação de pétalas, florzinhas etc. em muitas plantas. Uma rotação por esse ângulo pode ser aplicada repetidamente ao colocar pontos em torno de um círculo e os pontos serão espaçados uniformemente (dentro de um fator constante).

James King

Como Knuth obteve A?

Respostas: