[lkml]   [2002]   [Jan]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: hashed waitqueues
    On January 5, 2002 02:39 am, William Lee Irwin III wrote:
    >>> 2 or 3 shift/adds is really not possible, the population counts of the
    >>> primes in those ranges tends to be high, much to my chagrin.

    On Sat, Jan 05, 2002 at 03:44:06AM +0100, Daniel Phillips wrote:
    >> It doesn't really have to be a prime, being relatively prime is also
    >> good, i.e., not too many or too small factors. Surely there's a multiplier
    >> in the right range with just two prime factors that can be computed with 3
    >> shift-adds.

    The (theoretically) best 64-bit prime with 5 high bits I found is:

    11673330234145374209 == 0xa200000000100001
    which has continued fraction of p/2^64
    = 0,1,1,1,2,1,1,1,1,1,1,1073740799,2,1,1,1,1,6,1,1,5,1023,1,4,1,1,3,3

    and the (theoretically) best 64-bit prime with 4 high bits I found is:
    11529215046068994049 == 0xa000000000080001
    which has continued fraction of p/2^64
    = 0,1,1,1,2,549754765313,1,1,1,1,1,4095,2,1,1,1,1,2,1,2

    (the continued fractions terminate after the points given here)

    Which of the two would be better should depend on whether the penalty
    against the distribution for the sixth term of the 4-bit prime is worse
    than the computational expense of the extra shift/add for the 5-bit prime.

    I need to start benching this stuff.

    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:0.022 / U:50.660 seconds]
    ©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site