lkml.org 
[lkml]   [2002]   [Jan]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    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 <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/

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