Messages in this thread | | | Date | Tue, 8 Jan 2002 10:44:26 -0800 | From | William Lee Irwin III <> | Subject | Re: hashed waitqueues |
| |
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 - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |