4
$\begingroup$

Is there a method which would allow me to precisely calculate length of the largest number which has been created during multiplying two numbers?
What I mean is this:

1258
* 2569
Multiplying the above we get:

11322 : this is result from multiplying 9 * 1258
75480: this is result from multiplying 6 * 1258 and one zero is added as a padding
629000:this is result from multiplying 5 * 1258 and two zeros are added as a padding
2516000: this is result from multiplying 2 * 1258 and three zeros are added as a padding
total = 11322 + 75480 + 629000 + 2516000 = 3231802 I'm interested in finding the length of the 2516000, which is is there a way which would allow me in advance (knowing lengths of two operands) calculate it's largest possible length (with padding zeros included)

  • 0
    By 'le$n$gth' do you mea$n$ 'number of digits'? In that case the longest intermediate sum will always be that resulting from multiplying the rightmost digit of the *smallest* number in the product by the *largest* number in the product, and then padding with zeros.2011-06-15

2 Answers 2

3

Given an $n$-digit number $A=a_{n-1}\cdots a_0=a_{n-1}10^{n-1}+\cdots+a_110^1+a_0$ (where $a_i\in\{0,\ldots,9\}$ and $a_{n-1}\neq0$) and an $m$-digit number $B=b_{m-1}\cdots b_0=b_{m-1}10^{m-1}+\cdots+b_110^1+b_0$ (where $b_i\in\{0,\ldots,9\}$ and $b_{m-1}\neq0$), the largest number produced in the multiplication $A\cdot B$ is going to be $b_{m-1}10^{m-1}\cdot A$. The length of this number is given by $\lfloor \log_{10}(b_{m-1}10^{m-1}\cdot A)\rfloor+1=$ $m+\lfloor\log_{10}(A)+\log_{10}(b_{m-1})\rfloor=$ $m+n-1+\lfloor\log_{10}(a_{n-1}.a_{n-2}\ldots a_0)+\log_{10}(b_{m-1})\rfloor$ However, depending on what $b_{m-1}$ is and what the digits of $A$ are, this will equal either $m+n-1$ or $m+n$. For example, if $A=111$ and $B=23$, then the largest number in the multiplication will be $2220$, which is of length 4; note that $4=3+2-1+\lfloor\log_{10}(1.11)+\log_{10}(2)\rfloor=3+2-1+\lfloor 0.3463\ldots\rfloor.$ However, if $A=999$ and $B=23$, then the largest number in the multiplication will be $19980$, which is of length 5; note that $5=3+2-1+\lfloor\log_{10}(9.99)+\log_{10}(2)\rfloor=3+2-1+\lfloor 1.300\ldots\rfloor$ So there is no way of predicting the exact length of the number you're interested in (the largest term occurring in the multiplication) knowing only the lengths of the two inputs $A$ and $B$. However, if the length of $A$ is $n$ and the length of $B$ is $m$, you can say that the length is either $m+n-1$, or $m+n$.

  • 0
    I really liked the answer given by Zev Chonoles. It explained everything in a way that is easily understandable and very useful to me. Given two numbers of size m and n respectively, now I know that their product will be of size m+n or m+n-1. I need this for a program. Even an estimate works for me. Thanks a lot! :)2013-06-29
0

The old-fashioned way would be to use base 10 logarithms.

The modern way would be to use scientific notation: $1.258 \times 10^3 \; \times \; 2.569 \times 10^3 = 3.231802 \times 10^6$ so you need seven digits when multiplying these two four digit numbers.

Since an $n$ digit positive number is $x \times 10^{n-1}$ for $1 \le x \lt 10$ and the product of two numbers each less than 10 is less than 100, you can generalise this to say that multiplying an $n$ digit positive integer by an $m$ digit positive integer needs $n+m$ or $n+m-1$ digits: take the former to be safe.