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...<br>
<br>Uwe<br><br><div class="gmail_quote">On Feb 10, 2008 10:44 PM, Thorkil Naur <<a href="mailto:naur@post11.tele.dk">naur@post11.tele.dk</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hello,<br><br>If the standard libraries provide such a function, I haven't found it. I must<br>admit that I haven't studied your code in detail. I usually do as follows for<br>integer logarithms, shamelessly stolen from the Haskell report:<br>
<br>> -- Integer log base (c.f. Haskell report 14.4):<br>><br>> imLog :: Integer->Integer->Integer<br>> imLog b x<br>> = if x < b then<br>> 0<br>> else<br>> let<br>
> l = 2 * imLog (b*b) x<br>> doDiv x l = if x < b then l else doDiv (x`div`b) (l+1)<br>> in<br>> doDiv (x`div`(b^l)) l<br><br>Best regards<br>Thorkil<br><div><div></div>
<div class="Wj3C7c"><br><br>On Monday 11 February 2008 07:15, Uwe Hollerbach wrote:<br>> Hello, haskellers,<br>><br>> Is there a fast integer base-2 log function anywhere in the standard<br>> libraries? I wandered through the index, but didn't find anything that<br>
> looked right. I need something that's more robust than logBase, it<br>> needs to handle numbers with a few to many thousands of digits. I<br>> found a thread from a couple of years ago that suggested there was no<br>
> such routine, and that simply doing "length (show n)" might be the<br>> best. That seems kind of... less than elegant. I've come up with a<br>> routine, shown below, that seems reasonably fast (a few seconds of CPU<br>
> time for a million-bit number, likely adequate for my purposes), but<br>> it seems that something with privileged access to the innards of an<br>> Integer ought to be even much faster -- it's just a simple walk along<br>
> a list (array?) after all. Any pointers? Thanks!<br>><br>> Uwe<br>><br>> > powi :: Integer -> Integer -> Integer<br>> > powi b e | e == 0 = 1<br>> > | e < 0 = error "negative exponent in powi"<br>
> > | even e = powi (b*b) (e `quot` 2)<br>> > | otherwise = b * (powi b (e - 1))<br>><br>> > ilog2 :: Integer -> Integer<br>> > ilog2 n | n < 0 = ilog2 (- n)<br>> > | n < 2 = 1<br>
> > | otherwise = up n (1 :: Integer)<br>> > where up n a = if n < (powi 2 a)<br>> > then bin (quot a 2) a<br>> > else up n (2*a)<br>> > bin lo hi = if (hi - lo) <= 1<br>
> > then hi<br>> > else let av = quot (lo + hi) 2<br>> > in if n < (powi 2 av)<br>> > then bin lo av<br>
> > else bin av hi<br>><br>> (This was all properly aligned when I cut'n'pasted; proportional fonts<br>> might be messing it up here.)<br></div></div>> _______________________________________________<br>
> Haskell-Cafe mailing list<br>> <a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>> <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
><br></blockquote></div><br>