Anomaly in mpn_sqrtrem and mpn_rottrem

[bodrato at mail.dm.unipi.it]

Ciao,

Il Lun, 8 Giugno 2015 10:15 am, Torbjörn Granlund ha scritto:
> I played some years ago with a loop computing A^(-0.5), which naturally
> becomes division-free.  An alternative would be to keep the current
> algorithm, but use the fact that the previous divisor is a damn good
> staring approximation to the new one, and use Newton to maintain an
> inverse to it.

If we use the rootrem algorithm for sqrt, we could even try to update the
squared value, we have s and s^2, we update s to s<<c+r, and we update the
squared value (s<<c+r)^2 shifting s^2 and adding 2sr<<c + r^2; maybe using
a karatsuba-like update sequence).

Regards,
mb

-- 
http://bodrato.it/papers