Exact Division

[Kevin Ryde]

Josh Liu <zliu2 at student.gsu.edu> writes:
>
> 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.

If it's what I'm thinking of then that's likely.  Niels and I have
both had goes at this, you don't need to go to the full 2^n, you can
trim limbs through the calculation to end up at the target size
exactly.

But I don't think we're certain of the best way to make use of (or
eliminate rather) the redundancy in the calculation.

> Next one multiplies this modular
> inverse by the dividend with modulo $2^{2^n}$ arithmetic to get the
> exact quotient.

Niels is looking at that.  But it's likely the current quadratic code
will be better on small sizes, and possibly depending on the relative
sizes of dividend and divisor.

Recognising a sub-quadratic algorithm is usually fairly easy, figuring
out the details of exactly when to use it is usually not.

> Is there any way to eliminate that $r m$ term?

I'm not aware of any.  (Or only with a gcdext.)

> I think that a binary search,

Sounds unlikely, but stranger things have happened.