[Haskell-cafe] fast integer base-2 log function?
Uwe Hollerbach
uhollerbach at gmail.com
Thu Feb 14 23:23:29 EST 2008
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
More information about the Haskell-Cafe
mailing list