I under stand the shifting but not why it will always give the right answer?
For Example:
1101 1011 X____ 1101 (1101 times 1) 1101 (1101 times 1, shifted once) 0000 (1101 times 0, shifted twice) 1101 (1101 times 1, shifted thrice)
+_________________________
10001111 (binary 143)It seems like 1011 is never even used? I appreciate all clarity on the subject thank you
$\endgroup$ 32 Answers
$\begingroup$$\begin{matrix} & & & & & 1&1&0&1\\ & & & &\times & \color{red}{\rm 1} & \color{purple}{\rm 0} & \color{blue}{\rm 1} & \color{green}{\rm 1} \end{matrix}$
$\begin{matrix} & & & & 1 & 1 & 0 & 1 & (1101 \times \color{green}{\rm 1}) \\ ~ & & & 1 & 1 & 0 & 1 & & (1101 \times \color{blue}{\rm 1} ~\text{shifted once})\\ ~ & & 0 & 0 & 0 & 0 & & & (1101 \times \color{purple}{\rm 0} ~\text{shifted twice})\\ + & 1& 1& 0 & 1 & & & & (1101 \times \color{red}{\rm 1} ~\text{shifted thrice}) \end{matrix}$
Then add in the usual way the result of 1113111, but the "3" needs to be converted to "11", making it 1121111, the "2" needs to be converted to "10", 1201111, another carry over as we convert this "2" into a "10", 2001111, and one final carryover to have the final answer of 10001111.
This works because the number "1011" is equal to the number "1000 + 000 + 10 + 1".
Since $(a+b)\cdot x = a\cdot x + b\cdot x$, we often think of breaking down multiplication into smaller easier to work with steps. In this case, having it so that every number we multiply by in the smaller steps has only a single nonzero digit.
$\endgroup$ 6 $\begingroup$Here is a proof by Induction. Let $a=a_1a_2...a_n$ and $b=b_1b_2...b_m$. Observe that $a$ (the same with $b$) can be written as: $a=a_1c_1+a_2c_2+...a_nc_n$ where $c_i$ has 1 in ith position (e.g. $c_4=1000$). Let $ab$ is the result of the product of a and b by grade school algorithm. $ab$ can be written as: $$a_1b_1c_1+a_1b_2c_2+a_1b_3c_3+ .... + a_1b_mc_m + a_2b_1c_2 + a_2b_2c_4 + .... + a_2b_mc_{2m} + ... = \sum_{i=1}^n\sum_{j=1}^ma_ib_jc_{ij}$$Note that $c_{ij}$ has 1 in the (i*j)th position.
For basis case: Choose $a=11$ and $b=01$, then $a=a_1(1)+a_2(10)$ and $b = b_1(1)+b_2(10)$. Now, $ab = a_1 b_1(1)+a_1b_2(10)+a_2b_1(10)+a_2b_2(1000)=(1)(1)(1)+(1)(0)(10)+(1)(1)(10)+(1)(0)(1000)=1+10=11$
The induction hypothesis. Suppose that $a$ with $n$ digits and $b$ with $m$ digits gives the product of ab. Now, we want to show that it holds for a with one extra digit and b with one extra digits, i.e. $\bar{a}\bar{b}$ be the new product of a and b with an extra digit in each of them.
Since we defined ab (see above) and the difference between $\bar a$ and $a$ is that $\bar a$ has n+1 digits whereas $a$ has n digits. Thus, $\bar ab= ab + a_{n+1}b_1c_{n+1} + a_{n+1}b_2c_{2(n+1)}+...+ a_{n+1}b_mc_{m(n+1)}$. By multiplication rule, each digit in $a$ must be multiplied by each digit in $b$. Since this is achieved in $\bar ab$ by the grade-school algorithm, then we are done here. Do the same with $\bar{a}\bar{b}$ as following: $\bar{a}\bar{b} =\bar{a}b + b_{m+1}a_1c_{m+1} + b_{m+1}a_2c_{2(m+1)} + ... + b_{m+1}a_{n+1}c_{(n+1)(m+1)}$. It is clear that the multiplication rule holds here, too. Thus, the proof is complete.
$\endgroup$
