The Magic Constant
August 8th, 2007 by webstersprodigy
The hash_long function is found a lot of places in the kernel. Amongst other places it is how PIDs are stored in a table.
The has_long function boils down to
unsigned long hash_long(unsigned long val, unsigned int bits)
{
unsigned long hash = val * 0x9e370001UL;
return hash >> (32 - bits);
}
When I stumbled across this I was curious as to where 0x9e370001 came from. After a bit of searching, I found this:
(from “Understanding the Linux Kernel”)
The Magic Constant
You might wonder where the 0xe370001 constant (= 2,654,404,609) comes from. This hash function is based on a multiplication of the index by a suitable large number, so that the result overflows and the value remaining in the 32-bit variable can be considered as the result of a modulus operation. Knuth suggested that good results are obtained when the large multiplier is a prime approximately in golden ration to 2^32 (32 bit being the size of x86 registers). Now, 2,654,404,609 is a prime near to 2^32 * (sqrt(5) -1)/2 that can also be easily multiplied by additions and bit shifts, because it is equal to 2^31 + 2^29 -2^25 -2^19-2^16+1.
In other words, pulled out of Knuth’s and other’s asses.
Seriously, do people just sit around thinking about this type of stuff? My guess would be yes, and hats off to them. All I know is my new favorite number is now 2,654,404,609.