GMP 4.4 remaining tasks

[bodrato at mail.dm.unipi.it]

>  * 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
1.

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?

Regards,
Marco

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
tests.

-- 
http://bodrato.it/papers/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: invert.c
Type: text/x-csrc
Size: 5911 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20091207/2c0ef59d/attachment.bin>