mpn_sqrtrem{1,2}

[Marco Bodrato]

Ciao,

Il Ven, 23 Dicembre 2016 5:22 pm, Adrien Prost-Boucle ha scritto:
> I now have the same API for my implementation and for the code I've taken
> from GMP.

As a contribution to this discussion, I did the same thing, but the other
direction.

The attached code contains a copy of mpn_sqrtrem{1,2} from our repository,
a copy of the sqrtrem2 code that Paul Zimmermann posted to this list (July
2016), and an adaptation of Adrien Prost-Boucle's sqrtrem2 to the API and
sintax currently used by this internal function of GMP.

The attached file is meant as a replacement for the tune/speed-ext.c file
in a GMP source tree. After replacement:

./configure ABI=64 && make && (cd tune;make speed-ext)

And the tune/speed-ext program will be ready to compare the speed of the
three implementations.

Two limitations: it works only with ABI=64, some measurements seem
sensible to the "precision" required for measures... this is unexpected to
me.

[bodrato at shell ~/gmp-repo]$ tune/speed-ext -s2 -cp1000000000 mpn_sqrtrem2
pz_sqrtrem2 apb_sqrtrem2 mpn_sqrtrem
overhead 5.84 cycles, precision 1000000000 units of 2.86e-10 secs, CPU
freq 3500.07 MHz
         mpn_sqrtrem2   pz_sqrtrem2  apb_sqrtrem2   mpn_sqrtrem
2              106.08         95.39        #91.21        108.41

The abp function seems the faster one (at least on shell), but...

> However don't forget that nothing is fully checked nor proven in my
> implementation! It may still be wrong in some corner cases!

This is the biggest issue with the apb implementation... correctness
should be a prerequisite :-) but the promised speed is interesting.

Regards,
m

-- 
http://bodrato.it/papers/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: speed-ext.c
Type: text/x-csrc
Size: 23042 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20170128/476541a5/attachment-0001.bin>