Exact Division

[Josh Liu]

Exact division is currently an $O(n^2)$ process for GMP. Is the 
Jebelean paper on Karatsuba complexity exact division going to be 
implemented anytime soon? Is there a Toom-Cook analog to the Karatsuba 
exact division algorithm (I haven't read the paper yet, I really 
should)? Having a Toom-Cook algorithm for exact division would be a 
major breakthrough as it would allow exact division to have the same 
algorithmic analysis as multiplication. Finally, it would be best to 
use a 2-adic Newton-Hensel lifting method to compute the modular 
inverse of the divisor modulo $2^{2^n}$ where $2^n$ is larger than the 
base 2 logarithm of the dividend. Next one multiplies this modular 
inverse by the dividend with modulo $2^{2^n}$ arithmetic to get the 
exact quotient. Another problem that has tremendous applications is 
rather exact division can be generalized to inexact division without 
computing the reciprocal of the divisor. Basically the dividend can be 
written as $u=q v+r$, if one finds the modular inverse of $v$, $m$, and 
multiplies it by $u$, one obtains $u m = q + r m$. Is there any way to 
eliminate that $r m$ term? I think that a binary search, in conjunction 
with the computation of partial limbs of the actual quotient, is the 
best way to do inexact division using a modular inverse method.