Anomaly in mpn_sqrtrem and mpn_rottrem
tg at gmplib.org
Wed Jun 24 07:53:58 UTC 2015
bodrato at mail.dm.unipi.it writes:
I pushed a patch working for both even and odd sizes.
That's around 10% speedup, very nice!
To be honest, it's possible to further speed-up mpn_sqrt, replacing the
final divrem with a div_q. Expected timings follow:
9086 #5603297.21 7359423.00
25440 #22752715.40 28995848.50
71232 #81207275.50 100360485.00
But the code I'm experimenting with is not ready yet, it supports only
even sizes currently.
That's another 10% speedup.
My guess is that a division-free iteration would give another 10%, and
then using David's mulmid in that code would improve things by...10%.
Please encrypt, key id 0xC8601622
More information about the gmp-devel