Exact Division
Josh Liu
zliu2 at student.gsu.edu
Thu May 20 20:47:00 CEST 2004
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.
More information about the gmp-devel
mailing list