Thu Mar 30 18:03:48 CEST 2006
You are right! I did not think about that.
But bignum multiply by smallnum would require
O(MM) multiplications plus O(MM) additions with carry
where MM is the number of bignum digits (halfwords
in the erlang implementation) in the bignum. So
the bignum multiplication would be O(log(M)) itself.
The comparision would be like a bignum addition
which I guess also would be O(MM).
Would that result in O(MM*MM) => O(log(M)*log(M))?
Note: M > N could be optimized by first checking sign
and then comparing number of bignum digits
followed by comparision on highest bignum digit,
which would be O(1) unless they differ in worst
case the lowest digit which would be O(MM). This
since bignums are represented as a flexible number
of bignum digits (halfwords) of which the highest
must not be zero...
...Now I checked the code, that was the implementation!
(Matthias Lang) writes:
> 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.
/ Raimo Niskanen, Erlang/OTP, Ericsson AB
More information about the erlang-questions