[Haskell-cafe] How to calculate de number of digits of an integer?
Henning Thielemann
schlepptop at henning-thielemann.de
Sat Aug 29 19:12:22 EDT 2009
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.
More information about the Haskell-Cafe
mailing list