Thanks, guys! It looks at first glance as if the code Thorkil posted is similar to mine (grow comparison number in steps of 2 in the exponent, then binary-search to get the exact exponent), while Stefan's version is more similar to the walk-the-list idea I had in mind. I'll play with both of these when I get a chance...
Uwe On Feb 10, 2008 10:44 PM, Thorkil Naur <[EMAIL PROTECTED]> wrote: > 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 > > >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe