Re: hashed waitqueues

William Lee Irwin III
2002-01-08T18:45:15Z

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