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

    Trying to keep the factors even will probably be difficult, if you were
    going to sieve for it you'd probably want to try sieving with various
    polynomials something like the quadratic sieving factorization methods,
    in order to start from a list of candidates with sparse bit patterns.
    Or one can just iterate and filter by population counts...

    On Sat, Jan 05, 2002 at 03:44:06AM +0100, Daniel Phillips wrote:
    > Right, it's not worth it unless you can get it down to a handful of
    > shift-adds. How does 2**17 - 1 (Mersenne prime #6) with right-shift by
    > (16 - bits) work?

    I haven't started benchmarking different hash functions yet. Also
    interesting would be Fermat prime #4. The ratio phi falls in the
    range 4/7 < theta < 2/3, so perhaps to be sparse a slight overestimate
    like a prime in the range 0xA0000000 < p < 0xA7FFFFFF might be good.
    I did a little sieving for numbers in those ranges coprime to the small
    prime factors up to 29, and I found the natural numbers in this range
    with a population count strictly less than 5 are:

    $ factor `./prime`
    2483027969: 2483027969
    2684354593: 43 61 1023391
    2684355073: 101 139 367 521
    2684362753: 2684362753
    2684485633: 2684485633
    2717908993: 2717908993

    of these, 2684362753/2^32 differs by a mere 0.69679% from phi, and
    so appears to be the most promising. It has a population count of
    precisely 4. Among the numbers >= 0xA0000000, there was a consistent
    pattern of the hexadecimal digits, which was interesting. It is
    unfortunate, though, that among those primes there are none with
    population counts less than 4.

    The continued fraction expansion of 2684362753/2^32 appears to be:
    0, 1, 1, 1, 2, 8190, 1, 1, 1, 2, ... which has the disturbing
    sixth term, where on the other hand, theta is better for the seemingly
    further away ones:
    2483027969/2^32: 0, 1, 1, 2, 1, 2, 3, 1048575, 1, 2
    2684485633/2^32: 0, 1, 1, 1, 2, 511, 1, 1, 1, 1
    2717908993/2^32: 0, 1, 1, 1, 2, 1, 1, 1, 1, 1

    So in the continued fraction representation, 2717908993/2^32 is the
    closest to phi (though I am concerned about the term 262143 further out),
    and so 2717908993 is probably the best bet. I'll try these out and see
    if there is a significant difference in computational expense or key
    distribution.


    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:18    [W:0.044 / U:32.760 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site