Messages in this thread | | | Date | Fri, 4 Jan 2002 21:06:11 -0800 | From | William Lee Irwin III <> | Subject | Re: 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/
| |