fast inversion

[bodrato at mail.dm.unipi.it]

Ciao Paul,

Il Lun, 27 Aprile 2015 4:37 pm, paul zimmermann ha scritto:
> Please tell me if you find a faster version of the code.

Using tune/speed, the current code in GMP seems faster than the .c code
you published. But this does not mean that the algorithm is faster.
It depends, I suppose, on the fact that GMP code is tuned, uses some
low-level tricks and exploit modular multiplication.

Your code and the current GMP code (based on your previous work) are
equivalent wrt super-linear costs. It only tries to reduce the O(n) cost.
Maybe it's not worth the code involution, but it was fun writing it.

I applied most of the short-cuts to your special n==2 code, it's not as
readable as it was, but it should be faster. I attach a diff.

>> Il Mar, 3 Febbraio 2015 7:09 pm, paul zimmermann ha scritto:
>> > I did update my notes and code about fast inversion (which were used
>> as
>> > basis for Algorithm 3.5 ApproximateReciprocal in "Modern Computer

Regards,
marco

-- 
http://bodrato.it/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: invert.diff
Type: text/x-patch
Size: 2679 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20150507/db6644d1/attachment.bin>