Anomaly in mpn_sqrtrem and mpn_rottrem

Torbjörn Granlund tg at
Wed Jun 24 07:53:58 UTC 2015

bodrato at 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:
               mpn_sqrt   mpn_sqrtrem
  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 mailing list