fast special case of division?

[Paul Zimmermann]

> 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