Anomaly in mpn_sqrtrem and mpn_rottrem

[Torbjörn Granlund]

bodrato at mail.dm.unipi.it writes:

  Ciao,
  
  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...

-- 
Torbjörn
Please encrypt, key id 0xC8601622