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

[Daniel Peebles]

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<ekmett at 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 <uhollerbach at 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 at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>