Newbie questions

Matthias Lang matthias@REDACTED
Thu Mar 30 16:05:52 CEST 2006


Raimo Niskanen writes:
 > Regarding your problem about determining the number of decimal
 > digits in a number, I just came to think of a simple enough
 > brute force O(log(N)) or rather O(NN) where NN is the
 > number of digits in the number:
 > 
 >     digits(N) when is_integer(N), N >= 0 -> digits(N, 1, 0).
 > 
 >     digits(N, M, D) when M > N -> D;
 >     digits(N, M, D) -> digits(N, M*10, D+1).

I haven't ever studied bignum implementation, neither for Erlang or in
general, but I don't think this solution is O(log N).

I would expect M*10 to be expensive, i.e. O(M). And I'm not too sure
about the cost of the "M > N" test.

Matthias



More information about the erlang-questions mailing list