GMP 4.4 remaining tasks

bodrato at bodrato at
Mon Dec 7 00:22:06 CET 2009

>  * Write proper invert.c. Should use FFT wraparound, and optionally David
>    Harvey's mulmid. Perhaps also the mulmod_bnm1 trick. [40h]

I did try to write an invert.c using Newton's iterations... but I was not
able to get a correct and fast code.
The code I attach is faster than current one, but does not always give the
correct result. Among all values I tested (the 640000 of "try mpn_invert",
and some other), the function gives the correct answer 99.5% of the times.
The remaining 0.5% results are wrong, but can be corrected incrementing by

As far as I can see, currently mpn_invert is always launched with one more
limb; the added limb is then used to "round" the result and is removed.
The function I wrote seems good enough for this use, where a sporadic
minimal error will be "rounded away".

I didn't try to use any wraparound nor mulmid (we don't have it!), because
correctness was the first goal.

Comments or suggestions?


PS: the code I attach contains a #define DEBUG 1, with this enabled, a
final full check is performed on the final result; if it is not correct,
it is incremented by 1. With this "bug-remover", the function passes the
test "tets/devel/try mpn_invert", but it writes on screen for any
corrections, and it counts 2223 corrections needed to complete the 640,000

-------------- next part --------------
A non-text attachment was scrubbed...
Name: invert.c
Type: text/x-csrc
Size: 5911 bytes
Desc: not available
URL: <>

More information about the gmp-devel mailing list