Re: [Haskell-cafe] How to calculate de number of digits of an integer? (was: Is logBase right?)

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 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-... 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 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