Anomaly in mpn_sqrtrem and mpn_rottrem
tg at gmplib.org
Sat Jun 13 09:14:07 UTC 2015
bodrato at mail.dm.unipi.it 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 :-)
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.
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