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

Sat Aug 29 11:28:57 EDT 2009

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