Torbjörn Granlund tg at
Thu Mar 9 15:09:52 UTC 2017

"Marco Bodrato" <bodrato at> writes:

  >   After the patch.
  >   real	3m47.247s
  The time to compute and check 2^33 square roots, but it can be reduced.
Computing just 2^32 square roots would be another great speedup...

  > Almost 2x speedup, awesome!
  Yes, Adrien spotted a real problem. The sqrtrem2 function was "hidden"
  under a heavy wrapper. Needed for large operands, but too heavy for
  smaller ones.
  Now, I believe he will be able to gain another 2x improving sqrtrem2, I
  did not touch that core functions, only the wrappers !-)

And then another 2x might be gained by using the division-free iteration
(for A^{-0.5}) with mulhi/mullo/mulmid.

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list