[Haskell-cafe] How to calculate de number of digits of an integer?
Henning Thielemann
schlepptop at henning-thielemann.de
Tue Aug 25 11:01:24 EDT 2009
Bulat Ziganshin schrieb:
> Hello Henning,
>
> Tuesday, August 25, 2009, 6:11:00 PM, you wrote:
>
>>> digits = iterate (`div` 10) >>> takeWhile (>0) >>> length
>
>> This needs quadratic time with respect to the number of digits, doesn't
>> it?
>
> why?
Because division by 10 needs linear time.
> i think that `show` uses pretty the same way to build list of
> digits, so we just omit unneeded computations
I hope that 'show' will not need quadratic time but will employ a more
efficient algorithm that is certainly implemented in the GNU
multiprecision library. I assume that a division by 10^(2^k) will
require about 2^k * k operations. At least, it should be considerably
faster than repeatedly dividing by 10.
More information about the Haskell-Cafe
mailing list