[Haskell-cafe] fast integer base-2 log function?

[Uwe Hollerbach]

Hello, haskellers,

Is there a fast integer base-2 log function anywhere in the standard
libraries? I wandered through the index, but didn't find anything that
looked right. I need something that's more robust than logBase, it
needs to handle numbers with a few to many thousands of digits. I
found a thread from a couple of years ago that suggested there was no
such routine, and that simply doing "length (show n)" might be the
best. That seems kind of... less than elegant. I've come up with a
routine, shown below, that seems reasonably fast (a few seconds of CPU
time for a million-bit number, likely adequate for my purposes), but
it seems that something with privileged access to the innards of an
Integer ought to be even much faster -- it's just a simple walk along
a list (array?) after all. Any pointers? Thanks!

Uwe

> powi :: Integer -> Integer -> Integer
> powi b e | e == 0    = 1
>          | e < 0     = error "negative exponent in powi"
>          | even e    = powi (b*b) (e `quot` 2)
>          | otherwise = b * (powi b (e - 1))

> ilog2 :: Integer -> Integer
> ilog2 n | n < 0      = ilog2 (- n)
>         | n < 2      = 1
>         | otherwise  = up n (1 :: Integer)
>   where up n a = if n < (powi 2 a)
>                     then bin (quot a 2) a
>                     else up n (2*a)
>         bin lo hi = if (hi - lo) <= 1
>                        then hi
>                        else let av = quot (lo + hi) 2
>                             in if n < (powi 2 av)
>                                   then bin lo av
>                                   else bin av hi

(This was all properly aligned when I cut'n'pasted; proportional fonts
might be messing it up here.)