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

On Thu, Feb 14, 2008 at 8:23 PM, Uwe Hollerbach wrote:

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.

This seems wrong to me; that routine should take a small constant amount of time. I suspect you are measuring the time to construct the 50-million bit numbers as well. If you constructed a single number and called this routine on it several times I am sure you would get far different results, with the first routines taking ~7-11s each and Stefan's GHC/GMP-magic taking almost nothing. -- ryan