[Haskell-cafe] Fractional sqrt
naur at post11.tele.dk
Fri Jan 19 12:25:56 EST 2007
On Friday 19 January 2007 16:48, ajb at spamcop.net wrote:
> sqrtApprox' :: Integer -> Rational
> sqrtApprox' n
> | n < 0 = error "sqrtApprox'"
> | otherwise = approx n 1
> approx n acc
> | n < 256 = (acc%1) * approxSmallSqrt (fromIntegral n)
> | otherwise = approx (n `div` 256) (acc*16)
In the Haskell report section 14.4 (and also e.g. in GHC.Float), we find
-- Compute the (floor of the) log of i in base b.
-- Simplest way would be just divide i by b until it's smaller then b, but
-- be very slow! We are just slightly more clever.
integerLogBase :: Integer -> Integer -> Int
integerLogBase b i
| i < b = 0
| otherwise = doDiv (i `div` (b^l)) l
-- Try squaring the base first to cut down the number of divisions.
l = 2 * integerLogBase (b*b) i
doDiv :: Integer -> Int -> Int
doDiv x y
| x < b = y
| otherwise = doDiv (x `div` b) (y+1)
Something like this could probably be used to find a suitable sqrt
approximation for an Integer:
sqrtApproxViaLog i = 2^(integerLogBase 2 i `div`2)
More information about the Haskell-Cafe