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

[Uwe Hollerbach]

Hi, all, a few days ago I had asked about fast integer log-2 routines,
and got a couple of answers. I've now had a chance to play with the
routines, and here's what I found. Initially, Thorkil's routine taken
from the Haskell report was about 30% or so faster than mine. When I
replaced the calls to my routine "powi" with native calls to ^, my
routine became about 10% faster than Thorkil's routine. (I undoubtedly
had some reason for using my own version of powi, but I have no idea
anymore what that reason was... :-/ )

I initially thought that that speed difference might be due to the
fact that my routine had base 2 hard-wired, whereas his routine is for
general bases, but that seems not to be the case: when I modified my
version to also do general bases, it stayed pretty much the same. I
didn't do enough statistics-gathering to really be absolutely
positively certain that my routine is indeed 10.000% faster, but there
did seem to be a slight edge in speed there. Here's the latest
version, in case anyone's interested. I had previously had effectively
a bit-length version; since I made it general base-b I changed it to a
log function.

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

Stefan's routine is, as expected, much much faster still: I tested the
first two routines on numbers with 5 million or so bits and they took
~20 seconds of CPU time, whereas I tested Stefan's routine with
numbers with 50 million bits, and it took ~11 seconds of CPU time. The
limitation of Stefan's routine is of course that it's limited to base
2 -- it is truly a bit-length routine -- and I guess another potential
limitation is that it uses GHC extensions, not pure Haskell (at least
I had to compile it with -fglasgow-exts). But it's the speed king if
those limitations aren't a problem!

Uwe