update on mulmid-based inversion

bodrato at mail.dm.unipi.it bodrato at mail.dm.unipi.it
Sat Jan 9 15:46:54 CET 2010


> I agree. The MP algorithm and newton algorithm are actually very
> similar; the main difference is how to compute the middle portion of
> T = A X_h (notation as in algorithm "ApproximateReciprocal", Modern

I see. But current implementation (of the algorithm in the book) also uses
the lowest portion (I mean possible carries/borrows generated by it)...

> It might even be that the wraparound multiplication should be
> incorporated into mulmid! i.e. invertappr should always use
> mpn_mulmid, but the latter would use wraparound multiplication to
> implement the middle product for sufficiently large input.

Current implementation of mpn_ni_invertappr directly uses wraparound. I
feel it is better this way, instead of hiding wraparound properties behind
a different interface.

> Also, both algorithms would benefit from a better mulhi.

Of course, but one would like to have an exact mulhi...

Best regards,


More information about the gmp-devel mailing list