[lkml]   [2002]   [Jan]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: 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 <> and

    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.

    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    More majordomo info at
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 13:15    [W:3.386 / U:0.404 seconds]
    ©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site