GMP 4.4 remaining tasks

[David Harvey]

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

Hi,

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:

http://www.cims.nyu.edu/~harvey/mulmid/

Unfortunately I do not have time right now to work on this.

david