Newbie questions

[Raimo Niskanen]

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@REDACTED (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.
> 
> Matthias

-- 

/ Raimo Niskanen, Erlang/OTP, Ericsson AB