"Marco Bodrato" <bodr...@mail.dm.unipi.it> writes: > Sounds more interesting than binary euclid, to me. Because looking at the > lowest bits and just detecting the bit size seems easier than extracting > the highest bits each loop.
But it doesn't matter that much in which end bits are eliminated. Assume u,v odd, u > v, and we look for an update replacing u <-- u - q v. If u and v are the same bitsize, then u <-- u - v clears a bit in each end, and I don't think we can do much better, e.g, using u + v when that clears two bits at the low end seems to not gain much, since compared to u - v we lose about as much at the high end. If u is one bit larger than v, then plain euclid makes one bit of progress, while binary euclid makes two bits progress. Binary algorithm choosing between u-v and u+v also makes almost two bits of progress (worst case is when we use u+v and get a carry out. If u is two bits larger than v, then binary euclid makes three bits of progress, with q chosen from {3, 5, 7}. We can also make 3 bits of progress by setting q = -u v^{-1} (mod 8) with representatives from the set {±1, ±3} If u is k bits larger than v, k "large", then one can make k+1 bits of progress by a full euclidean or mod 2^{k+1} division. What Torbjörn suggests, I think, is to get a multiplier q' = u v^{-1} (mod 2^j) with j = 4 or so by table lookup, and then set q = 2^k + q'. Then we cancel j bits at the low end and 1 bit at the high end. My gut feeling is that it's not so useful to do something very clever for the case that k, the bit size difference between u and v, is large. It's a fairly unlikely case, we make decent progress if we just use the 2^j-sized table and get j bits of progress per iteration, and when the difference is large enough, it will pay off to just do a division operation (of either kind) producing a full k-bit quotient. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel