Golden Ratio & Hash Tables
Alexei A. Frounze
tables? Is it the only possible and effective value? I've not found anything
about this particular choice in the Sedgewick's book, just the fact that
it's used. Any simple explanation?
I believe Knuth has explanation, but I don't have the book handy and don't
know when I'll be able to read it. Can you explain why (sqrt(5)-1)/2, but
not let's say (sqrt(3)-1)/2? Does this really have anything to do with
Fibonacci numbers, packing of seeds and thelike?
TIA
--
Alexei A. Frounze
Hanford Carr
The golden ratio is (1+sqrt (5))/2
See the following for some explanations
http://www.friesian.com/golden.htm
If F(n) is a Fibonacci number
let R= F(n+1)/F(n) = (F(n)+F(n-1))/F(n) = 1 + F(n-1)/F(n)= 1+
1/(F(n)/F(n-1))
as n gets larger R gets closer and closer to F(n)/F(n-1)
R=1+1/R
R^2=R+1
R^2-R-1=0
R= (1+(+/-)sqrt(1-4(-1)))/2
R= (1+(+/-)sqrt(5))/2
Sorry don't have a clue to its application to hash tables.
cheers hanford
Larry Hammick
"Alexei A. Frounze"
> Can anybody enlighten me why golden ratio is so widely used when doing
hash
> tables? Is it the only possible and effective value? I've not found
anything
> about this particular choice in the Sedgewick's book, just the fact that
> it's used. Any simple explanation?
>
> I believe Knuth has explanation, but I don't have the book handy and don't
> know when I'll be able to read it. Can you explain why (sqrt(5)-1)/2,
> but not let's say (sqrt(3)-1)/2?
The golden ratio has the slowest-converging continued fraction expansion of
any real number, apart from trivial changes like adding an integer. I don't
know from hash tables, but that might be part of an answer.
> Does this really have anything to do with Fibonacci numbers,
Yes. There's plenty about this on the web.
> packing of seeds and the like?
Yes indeed. Coxeter wrote about it in his 1961 _Introduction to Geometry_.
Google with "phyllotaxis" and "golden" gets a few hundred hits.
Larry
Michele Dondi
<"hwcarr<nospam>"@lmc.attbbs.net> wrote:
>The golden ratio is (1+sqrt (5))/2
I might just be wrong, but is seems to me that some authors define the
golden ratio to be what you wrote, say, g, while others use
g'=g-1=1/g.
Since g.r. is a *ratio*, one could well consider it to be either g or
1/g, but in a certain sense there's and advantage in having it lying
in [0,1] which is an argument in favor of the 2nd choice...
Just my 2 cents,
Michele
--
Liberta' va cercando, ch'e' si' cara,
Come sa chi per lei vita rifiuta.
[Dante Alighieri, Purg. I, 71-72]
I am my own country - United States Confederate of Me!
[Pennywise, "My own country"]
Christopher Green
The usual explanation is that it provides the best dispersion of
consecutive keys in a multiplicative hash table: that was Knuth's
reason for advocating it.
For a hash table of size 2^N, an index for each key K can be
constructed by multiplying K * M, where M is a prime number close to
2^N * R, R being the inverse golden ratio (sqrt(5)-1)/2. Keep the N
most significant bits as the hash index. Knuth's finding was that the
dispersion of indexes for a sequence of consecutive keys is maximized
when M is chosen this way, thus a multiplicative hash table with a
dense set of keys will have the fewest possible collisions when M
approx= 2^N * R.
--
Chris Green