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@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
