fast special case of division?
Paul Zimmermann
Paul.Zimmermann at loria.fr
Tue Mar 6 15:59:50 CET 2007
> Suppose we want to do a truncated division n/d (n and d are mpz_t), where we know in advance that:
>
> 1. n>d>0
> 2. q=floor(n/d) is a small integer, most likely 1, and almost certainly it will fit in a limb.
>
> How can we get q as fast as possible? Is it best to just divide the most significant limbs of n and d, and correct q when it is wrong?
>
> Keith
Divide the 2 most significant limbs of n by the most significant limb of d.
Assuming d is normalized (i.e., its most significant bit is set) this will
yield either q, q+1 or q+2 where q is the exact quotient. See Section 1.4.1
of <http://www.loria.fr/~zimmerma/mca/pub226.html>.
Alternatively you can divide the 3 msbs of n by the 2 msbs of d. This idea
mentioned to me by Torbjörn Granlund and Niels Möller yields q with very
high probability (q+1 is produced only with probability 2^(-32) or 2^(-64)).
Paul Zimmermann
More information about the gmp-discuss
mailing list