Although this isn't a very "general approach", I just submitted a patch to GHC (not yet merged) with a gmp binding to mpz_sizeinbase, which would allow for very quick computation of number of digits in any base.
On Sat, Aug 29, 2009 at 9:12 PM, Edward Kmett<ekm...@gmail.com> wrote: > I have a version of this inside of the monoid library buried in the > Data.Ring.Semi.BitSet module: > http://comonad.com/haskell/monoids/dist/doc/html/monoids/src/Data-Ring-Semi-BitSet.html#hwm > To do any better by walking the raw Integer internals you need to know the > 'finger' size for the GMP for your platform, which isn't possible to do > portably. > -Edward Kmett > > On Wed, Aug 26, 2009 at 10:42 AM, Uwe Hollerbach <uhollerb...@gmail.com> > wrote: >> >> Here's my version... maybe not as elegant as some, but it seems to >> work. For base 2 (or 2^k), it's probably possible to make this even >> more efficient by just walking along the integer as stored in memory, >> but that difference probably won't show up until at least tens of >> thousands of digits. >> >> Uwe >> >> ilogb :: Integer -> Integer -> Integer >> ilogb b n | n < 0 = ilogb b (- n) >> | n < b = 0 >> | otherwise = (up 1) - 1 >> where up a = if n < (b ^ a) >> then bin (quot a 2) a >> else up (2*a) >> bin lo hi = if (hi - lo) <= 1 >> then hi >> else let av = quot (lo + hi) 2 >> in if n < (b ^ av) >> then bin lo av >> else bin av hi >> >> numDigits n = 1 + ilogb 10 n >> >> [fire up ghci, load, etc] >> >> *Main> numDigits (10^1500 - 1) >> 1500 >> *Main> numDigits (10^1500) >> 1501 >> _______________________________________________ >> 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 > > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
