Mod operation

[Paul Zimmermann]

       Niels,

> >> I also wonder if there's some clever way to compute the inverse and m3
> >> simultaneously (they're quotient and remainder of B^3 / m). The
> >> "obvious" way is newton iteration to get the quotient aka inverse, and
> >> anothere multiplication to get the remainder, but maybe they can be
> >> combined in the final newton step or something like that.
> >
> > you can do this by calling the recursive division with dividend B^3 and
> > divisor m. This is exactly half the work done by the recursive division
> > for (4n)/(2n), i.e., (3n)/(2n), and will cost 3M(n) in the Karatsuba range.
> 
> How does this compare to computing the inverse, floor (B^2 / m_1),
> using Newton iteration? I.e., what's the additional cost for also
> computing the remainder B^3 mod m?

basically you need a short division D*(n) (with quotient only) to compute the
quotient, then an FFT of length 2n, i.e., M(n), will suffice to recover
the remainder, since you know the upper n limbs will cancel with B.

Thus you have to compare D*(n)+M(n) with 1/2 DC(2n), where DC(2n) = 2 DC(n)
+ 2 M(n), thus to compare D*(n)+M(n) with DC(n) + M(n). It thus seems that
if D*(n) <= DC(n), you'd better use Newton's method (assuming you can use
the wrap-around trick).

Paul