`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 weregoing to sieve for it you'd probably want to try sieving with variouspolynomials 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. Alsointeresting would be Fermat prime #4. The ratio phi falls in therange 4/7 < theta < 2/3, so perhaps to be sparse a slight overestimatelike a prime in the range 0xA0000000 < p < 0xA7FFFFFF might be good.I did a little sieving for numbers in those ranges coprime to the smallprime factors up to 29, and I found the natural numbers in this rangewith a population count strictly less than 5 are:\$ factor `./prime`2483027969: 24830279692684354593: 43 61 10233912684355073: 101 139 367 5212684362753: 26843627532684485633: 26844856332717908993: 2717908993of these, 2684362753/2^32 differs by a mere 0.69679% from phi, andso appears to be the most promising. It has a population count ofprecisely 4. Among the numbers >= 0xA0000000, there was a consistentpattern of the hexadecimal digits, which was interesting. It isunfortunate, though, that among those primes there are none withpopulation 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 disturbingsixth term, where on the other hand, theta is better for the seeminglyfurther away ones:2483027969/2^32: 0, 1, 1, 2, 1, 2, 3, 1048575, 1, 22684485633/2^32: 0, 1, 1, 1, 2, 511, 1, 1, 1, 12717908993/2^32: 0, 1, 1, 1, 2, 1, 1, 1, 1, 1So in the continued fraction representation, 2717908993/2^32 is theclosest 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 seeif there is a significant difference in computational expense or keydistribution.Cheers,Bill-To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgMore majordomo info at  http://vger.kernel.org/majordomo-info.htmlPlease read the FAQ at  http://www.tux.org/lkml/`