Hello, On Friday 19 January 2007 16:48, ajb@spamcop.net wrote:
... sqrtApprox' :: Integer -> Rational sqrtApprox' n | n < 0 = error "sqrtApprox'" | otherwise = approx n 1 where 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 that would -- 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 where -- 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) Best regards Thorkil