Jak Knuth wyprowadził A?

Interpretując klucze jako liczby naturalne, możemy użyć następującej formuły.

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

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

Trudno mi zrozumieć, w jaki sposób wybieramy wartość A, gdzie:

0 < A < 1

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

Według Knutha optymalna wartość to:

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

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

Więc moje pytanie brzmi: jak do tego doszedł Knuth i jak mogę obliczyć optymalną wartość dla moich konkretnych danych?

hash-function ChaosPandion
źródło

Po prostu uważam za interesujące, że ... i googlowanie, które faktycznie przyniosło odniesienie do „Knuth twierdzi, że wielokrotne mnożenie przez złoty współczynnik zminimalizuje luki w przestrzeni mieszania, a zatem jest to dobry wybór do łączenia razem wiele kluczy, aby utworzyć jeden ”.

A = 1 + ϕ

$A = 1+\phi$

Ahmed Masud

Jeśli dobrze pamiętam, wyjaśniono to w jednym z ćwiczeń, w którym sensie są ładnie rozłożone w przedziale jednostkowym. Jednak nie mam teraz książki do sprawdzenia.

k A \mod 1

$kA \mod 1$

Radu GRIGore

@RaduGRIGore to dobrze znane twierdzenie, że jest równomiernie rozłożonym modułem dla dowolnego irracjonalnego (twierdzenie 6.3 „Liczb nieracjonalnych” Niven). Być może jest w pewnym sensie najlepszym wyborem.

A, 2 A, \dots

$A, 2A, \ldots$

1

$1$

A

$A$

A = 1 + ϕ

$A=1+\phi$

zrobił

Nie ma czegoś takiego jak „bardziej optymalny”; to tak, jakby powiedzieć „lepiej”. Albo jest to optymalna wartość, albo nie.

Jeffε

Warto zauważyć, że z tej wartości korzystają również naturalne procesy. W szczególności złoty kąt reguluje umieszczanie płatków, różyczek itp. W wielu roślinach. Obracanie o ten kąt może być stosowane wielokrotnie podczas umieszczania punktów wokół koła, a punkty będą równomiernie rozmieszczone (w ramach stałego współczynnika).

James King

Jak Knuth wyprowadził A?

Odpowiedzi: