[Math] Calculate the number of digits in a product of large numbers

algorithmsnumber theory

I'm looking for a method that can calculate the number of digits in a product of several large numbers. For example, calculate the number of digits in the product 4*51*6001*70001*800001*9000001? I know the basic technique is to factor out tens, but I would like to know some details about this method. Thank you all!

Best Answer

For the general case, you should consider the base 10 logarithm of the number. It should be easy to simplify things since $\log_{10}{ab} = \log_{10}{a} + \log_{10}{b}$.

But since calculators are not allowed for your specific example, we'll have to do it a bit differently. The product in your specific example is roughly equals to $4 \times 50 \times 6000 \times 70000 \times 800000 \times 9000000$. I guess its easier to calculate the number of digits from here on, and probably the only way (AFAIK) to do it without a calculator for your specific example.

Related Solutions

[Math] Calculate the root of a number without useing the root function or decimal numbers

Yes it can be done.
Suppose that you are given $n$, you want to calculate $\lceil \sqrt{n} \rceil$, so you can apply a binary search algorithm with $k^2 \geq n \land (k-1)^2 < n$ as the stopping condition. $k$ here is the variable over which you are doing the binary search. The algorithm would be like this:

low = 0
top = n
while(true)
  mid = (low+top)/2
  if(mid*mid >= n and (mid-1)*(mid-1) < n)
    return mid
  else
    if(mid*mid < n)
      low = mid + 1
    else
      top = mid-1
    end
  end
end

[Math] How to calculate modulo of large integer (number having 25000 digits)

As small as your modulus is, I don't think you can do significantly better than ordinary long division (typically done in base $2^{64}$) to compute the remainder.

However, you can optimize the individual steps; e.g. by using an algorithm like Barrett reduction to obtain the remainder of a 2 digit x 1 digit remainder calculation.

Writing efficient (or even simply correct) division code is a very irritating task; unless you really, really like this sort of programming or are using a specialized algorithm for a very special case, you are certainly better off with a good (or even just decent) bignum package.

Best Answer

Related Solutions

[Math] Calculate the root of a number without useing the root function or decimal numbers

[Math] How to calculate modulo of large integer (number having 25000 digits)

Related Question