Author: Heiner Marxen

Date: 14:37:27 02/18/02

Go up one level in this thread

On February 18, 2002 at 17:07:11, Dann Corbit wrote: >On February 18, 2002 at 16:56:37, Benny Antonsson wrote: > >>Why must it be a prime number ? > >When a composite number is chosen, factors in the number can cause a bad >[non-uniform] distribution. > >See Knuth's "The Art of Computer Programming", Volume 3 'Sorting and Searching' >page 516 for a detailed explanation. IMO this is only an issue if you start with a non-uniform distribution. If your hash key is already very good (Zobrist should be good enough), you may take any hash table size and do hash_index = hash_key % hash_table_size; (After all, taking the low N bits is just an efficient way to do key % (1<<N)) In doubt (probably anyhow) just measure the quality of the distribution. It is of high quality, it behaves similar to a true random distribution. Many years ago I've done such experiments, but I do not remember the details any more, sorry. Cheers, Heiner

- Re: Non power of two hash table sizes
**Dann Corbit***15:58:54 02/18/02*- Re: Non power of two hash table sizes
**Heiner Marxen***17:19:17 02/18/02*- Re: Non power of two hash table sizes
**Dan Andersson***23:47:41 02/18/02*- Re: Non power of two hash table sizes
**Heiner Marxen***06:23:18 02/19/02*- Re: Non power of two hash table sizes
**Dan Andersson***11:21:15 02/19/02*

- Re: Non power of two hash table sizes

- Re: Non power of two hash table sizes
- Re: Non power of two hash table sizes
**Dann Corbit***17:34:09 02/18/02*- Re: Non power of two hash table sizes
**Keith Evans***15:11:20 02/19/02*

- Re: Non power of two hash table sizes

- Re: Non power of two hash table sizes

- Re: Non power of two hash table sizes

This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.