Messages in this thread | | | Date | Tue, 8 Jan 2002 10:20:37 -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.
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.
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/
| |