[Haskell-cafe] How to calculate de number of digits of an integer?

[Henning Thielemann]

Bulat Ziganshin schrieb:
> Hello Henning,
> 
> Tuesday, August 25, 2009, 7:01:24 PM, you wrote:
> 
>> I hope that 'show' will not need quadratic time but will employ a more
>> efficient algorithm
> 
> yes, you are right

I thought a little about it. If I had to implement that in GMP it could
be done quite fast in many cases: Count the number of bits, say it is
'k' and multiply with logBase 10 2. If 2^k and 2^(k+1)-1 have the same
number of decimal digits, we are done. Otherwise we have to process some
of the most significant bits. If the number is between n*2^k and
(n+1)*2^k-1 and both bounds have the same number of decimal digits
(logBase 10 n + k * logBase 10 2), we are also done. Only for numbers
close to powers of 10 we have to process the whole integer.