Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
Don't you mean the length of the product? It seems odd to ask for the longest number which appears when multiplying. Why do you need this for? For an implementation on the computer? You could try some thing like this: the length of a number $N$ is $\lfloor \log_{10}N \rfloor +1$. When multiplying two numbers the length of the product can be predicted with an error of $\pm 1$, but I think the only way to know this precisely is by calculating the product, or making the operations with logarithms presented above. –  Beni Bogosel Jun 15 '11 at 8:47
    
By 'length' do you mean '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. –  Chris Taylor Jun 15 '11 at 8:49
add comment

2 Answers

up vote 3 down vote accepted

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$.

share|improve this answer
    
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! :) –  user84336 Jun 29 '13 at 1:32
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.