Re: hashed waitqueues

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

William> On Tue, Jan 08, 2002 at 10:20:37AM -0800, William Lee Irwin III wrote:
>> The (theoretically) best 64-bit prime with 5 high bits I found is:
William> 	[numbers]
>> and the (theoretically) best 64-bit prime with 4 high bits I found is:
William> 	[numbers]
William> Sorry, I forgot to credit my helpers in the last post:
William> The sieving technique to find these things was devised by
William> Christophe Rhodes <csr21@cam.ac.uk> and fare@tunes.org

On Tue, Jan 08, 2002 at 10:40:33AM -0800, Roland Dreier wrote:
> Just out of curiousity, why do you need a "sieving technique" to find
> these primes?  There are only 63 choose 4 (which is 595665) 64 bit
> numbers with only 5 bits set, of which probably no more than 15000 are
> prime, so it seems you could just test all of them.  What am I missing?

The sieving technique they devised uses that. In fact, they search only
2*choose(59,2), as bits 63, 0, and one of either 60 or 61 must be set,
since it must be odd to be prime and bits 63 -> 60 are determined by
(up to the choice of either 60 or 61) by 4/7 <= p/2^64 <= 2/3.


Cheers,
Bill