GMP 4.4 remaining tasks
dmharvey at cims.nyu.edu
Mon Dec 7 15:23:25 CET 2009
On Dec 6, 2009, at 6:22 PM, bodrato at mail.dm.unipi.it wrote:
>> * 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
> and some other), the function gives the correct answer 99.5% of the
> 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
> 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!),
> correctness was the first goal.
About a month ago I wrote some approximate reciprocal code using the
middle product. It's well-tested, and it *should* be pretty fast (at
least on K8 where good middle product basecase assembly code is
available), but I have not profiled it yet. I was planning to post it
once I had some performance figures, but since this has come up now
on gmp-devel I thought I would post it now:
Unfortunately I do not have time right now to work on this.
More information about the gmp-devel