Thorkil Naur naur at post11.tele.dk
Fri Jan 19 12:25:56 EST 2007

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