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

[Uwe Hollerbach]

Ouch! That is indeed an improvement... I don't recall all the details
of this codelet, but I think I got the seed off the net somewhere
(perhaps this list?), and it might well have been better originally.
So, brightly brightly and with beauty, I probably executed a
verschlimmbesserung. After a year and a half, I find I still have
almost no intuition about performance issues in haskell... guess I
have to practice more.

Uwe

On 8/29/09, Bertram Felgenhauer <bertram.felgenhauer at googlemail.com> wrote:
> 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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>