ajb at spamcop.net ajb at spamcop.net
Sun Aug 24 21:07:53 EDT 2008

G'day all.

Quoting Daniel Fischer <daniel.is.fischer at web.de>:

> The good fix is to insert calls to the apprpriate conversion function where
> necessary, for example
>
> sqRoot n scale = sqRoot' (5*n) 5
>   where
>   sqRoot' a b
>     | floor (logBase 10 \$ fromIntegral b) >= scale = div b 10
>     | a >= b    = sqRoot' (a-b) (b+10)
>     | otherwise = sqRoot' (a*100) ((100 * (div b 10)) + (mod b 10))

The problem here is that floating-point numbers do not have arbitrary
precision, whereas Integers do.  For very large numbers, the
conversion might not be possible.

Option #1:

sqRoot n scale = sqRoot' (5*n) 5
where
sqRoot' a b
| b >= invScale = div b 10
| a >= b    = sqRoot' (a-b) (b+10)
| otherwise = sqRoot' (a*100) ((100 * (div b 10)) + (mod b 10))
invScale = 10^scale

Option #2:

sqRoot n scale = sqRoot' (5*n) 5
where
sqRoot' a b
| length (show b) >= scale = div b 10  -- May be an off-by-one error here.
| a >= b    = sqRoot' (a-b) (b+10)
| otherwise = sqRoot' (a*100) ((100 * (div b 10)) + (mod b 10))

Sadly, option #2 (and option #3, not shown, which is essentially to
implement your own integer-only floor-log-base-10) destroys the
pretty "mostly subtraction only" property of the algorithm.

Cheers,
Andrew Bromage