Square root and double rounding

[uunet!cwi.nl!Dik.Winter]

I found another thing interesting, and it is a bit related.  I never
came to study the rounding situation but I did study the situation
where arithmetic is truncating.  In that case to get the p-bit square
root it is sufficient to do Newton iteration with p-bit truncating
arithmetic except for exactly two different mantissa's (similar to
those in Priest's posting).  In most cases the iteration would converge
to a single mantissa, in the exceptional cases ultimately the iteration
would alternate between the two surrounding representable values.  To
get ultimate convergence for those you need 2p bits of precision.  I
think the situation in the rounding case is very similar (but some more
bits required, i.e. replacing 2p by 2p+2 and so on).  Implementations
can use it if they do Newton.  Do the minimal precision for Newton and
special case the two exceptional values.

dik
--
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924098
home: bovenover 215, 1025 jn  amsterdam, nederland; e-mail: dikacwi.nl