[Haskell-cafe] fast integer base-2 log function?
Uwe Hollerbach
uhollerbach at gmail.com
Mon Feb 11 12:55:06 EST 2008
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 <naur at post11.tele.dk> 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 at haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080211/90e9a04b/attachment.htm
More information about the Haskell-Cafe
mailing list