Newbie questions
Matthias Lang
matthias@REDACTED
Thu Mar 30 17:51:59 CEST 2006
Matthias Lang 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.
Er, that's wrong too.
Bignum multiplication must be implemented as some sort of
shift-and-add. Which would make it O(log M), not O(M) as I said.
So I expect there to be log M multiplications, each costing log
M. That makes the whole thing O(log N * log N).
Matthias
More information about the erlang-questions
mailing list