Anomaly in mpn_sqrtrem and mpn_rottrem

Torbjörn Granlund tg at
Sat Jun 13 09:14:07 UTC 2015

bodrato at writes:

  Il Ven, 12 Giugno 2015 9:04 am, Torbjörn Granlund ha scritto:
  > We might want to look into the plain division-free sqrt(A) = A*sqrt(1/A)
  > approach before implementing a tricky division sqrt(A).
  We can try improving the current implementation, before implementing any
  other algorithm :-)
You're wise.

  I wrote a simple patch (it touches very few lines) that allows skipping
  the final squaring when mpn_sqrtrem is called with a NULL argument and the
  approximation computed so far can not change.
  It exploits the spurious half-a-limb that current code adds to the result
  when the size is odd, i.e. it changes the timings only for odd sizes.
Nice speedup!

I suppose we really ought to add a limb also for even sizes (at least
when computing with more than a few limbs) to allow for this type of
speedup for even operand sizes too...

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list