[Haskell-cafe] How to calculate de number of digits of an integer? (was: Is logBase right?)

[Bertram Felgenhauer]

Uwe Hollerbach wrote:
> Here's my version... maybe not as elegant as some, but it seems to
> work. For base 2 (or 2^k), it's probably possible to make this even
> more efficient by just walking along the integer as stored in memory,
> but that difference probably won't show up until at least tens of
> thousands of digits.
> 
> Uwe
> 
> ilogb :: Integer -> Integer -> Integer
> ilogb b n | n < 0      = ilogb b (- n)
>           | n < b      = 0
>           | otherwise  = (up 1) - 1
>   where up a = if n < (b ^ a)
>                   then bin (quot a 2) a
>                   else up (2*a)
>         bin lo hi = if (hi - lo) <= 1
>                        then hi
>                        else let av = quot (lo + hi) 2
>                             in if n < (b ^ av)
>                                   then bin lo av
>                                   else bin av hi

We can streamline this algorithm, avoiding the repeated iterated squaring
of the base that (^) does:

-- numDigits b n | n < 0 = 1 + numDigits b (-n)
numDigits b n = 1 + fst (ilog b n) where
    ilog b n
        | n < b     = (0, n)
        | otherwise = let (e, r) = ilog (b*b) n
                      in  if r < b then (2*e, r) else (2*e+1, r `div` b)

It's a worthwhile optimization, as timings on n = 2^1000000 show:

    Prelude T> length (show n)
    301030
    (0.48 secs, 17531388 bytes)
    Prelude T> numDigits 10 n
    301030
    (0.10 secs, 4233728 bytes)
    Prelude T> ilogb 10 n
    301029
    (1.00 secs, 43026552 bytes)

(Code compiled with -O2, but the interpreted version is just as fast; the
bulk of the time is spent in gmp anyway.)

Regards,

Bertram