Hello, If the standard libraries provide such a function, I haven't found it. I must admit that I haven't studied your code in detail. I usually do as follows for integer logarithms, shamelessly stolen from the Haskell report:
-- Integer log base (c.f. Haskell report 14.4):
imLog :: Integer->Integer->Integer imLog b x = if x < b then 0 else let l = 2 * imLog (b*b) x doDiv x l = if x < b then l else doDiv (x`div`b) (l+1) in doDiv (x`div`(b^l)) l
Best regards Thorkil On Monday 11 February 2008 07:15, Uwe Hollerbach wrote:
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.) _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe