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