[Haskell-cafe] Fractional sqrt

[Thorkil Naur]

Hello,

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
>     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