Re: hashed waitqueues

[William Lee Irwin III <wli@holomorphy.com>]

On January 5, 2002 02:39 am, William Lee Irwin III wrote:
>>> 2 or 3 shift/adds is really not possible, the population counts of the
>>> primes in those ranges tends to be high, much to my chagrin.

On Sat, Jan 05, 2002 at 03:44:06AM +0100, Daniel Phillips wrote:
>> It doesn't really have to be a prime, being relatively prime is also 
>> good, i.e., not too many or too small factors.  Surely there's a multiplier 
>> in the right range with just two prime factors that can be computed with 3 
>> shift-adds.

The (theoretically) best 64-bit prime with 5 high bits I found is:

11673330234145374209 == 0xa200000000100001
which has continued fraction of p/2^64
	= 0,1,1,1,2,1,1,1,1,1,1,1073740799,2,1,1,1,1,6,1,1,5,1023,1,4,1,1,3,3

and the (theoretically) best 64-bit prime with 4 high bits I found is:
11529215046068994049 == 0xa000000000080001
which has continued fraction of p/2^64
	= 0,1,1,1,2,549754765313,1,1,1,1,1,4095,2,1,1,1,1,2,1,2

(the continued fractions terminate after the points given here)

Which of the two would be better should depend on whether the penalty
against the distribution for the sixth term of the 4-bit prime is worse
than the computational expense of the extra shift/add for the 5-bit prime.

I need to start benching this stuff.


Cheers,
Bill