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 > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe > _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
