[Haskell-cafe] fast integer base-2 log function?

[Thorkil Naur]

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>