[Haskell-beginners] Puzzling type error
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
More information about the Beginners
mailing list