Proof of a different (Russian peasant) method of multiplication

Question

I got this problem in the book Topics in the Theory of Numbers by Paul Erdos and Janos Suranyi and I found it very interesting. I have no idea how to prove this. (Although I believe it can be proved by a lot of methods.)

All I could conclude was the following:

• If $A$ and $B$ are two numbers, this method sums the quantity $[\frac{A}{2^i}]\cdot2^iB$ only when the greatest integer function has odd value. (There will be only a finite number of terms as $[\frac{A}{2^i}]$ will eventually become $0$ after some $i>i_0.$)
• I also tried writing $A$ and $B$ in the form as $A= \sum_{i=0}^{n} a_i\cdot10^i$ and $B= \sum_{j=0}^{m} b_j\cdot10^j$ but could not reach to any conclusion.

Any sort of help is appreciated.

Also, I would like to know how efficient is this method for calculating the product of two numbers in computer algebra systems (for example PARI/GP) compared to the other methods currently being used?

Answer 1

That is essentially writing the first number in binary:

$\begin{equation*} A = \sum_i a_i \cdot 2^i \end{equation*}$

The $a_i$ are 1 whenever the respective row's number under $A$ is odd. As you observe, this adds in $2^i B$, if $a_i = 1$, so:

$\begin{equation*} S = \sum_i a_i \cdot 2^i \cdot B = A \cdot B \end{equation*}$

Answer 2

We have

$$73_d=1001001_b=2^6+2^3+2^0.$$

We perform the conversion by checking the parity, then dividing by two ($73$ odd $\to36$ even $\to18$ even $\to\cdots$).

To obtain the product, we add $$(2^6+2^3+2^0)\cdot217=(2^6\cdot217)+(2^3\cdot217)+(2^0\cdot217),$$ where the terms are computed by successive doublings.

The key equation is $$A\cdot B=\left(\sum_{k=1}^l2^{a_k}\right)\cdot B=\sum_{k=1}^l(2^{a_k}\cdot B)$$ where $a_k$ denotes the rank of the nonzero bits.

---

Note that this is not essentially different from the classical method, where we decompose the multiplier in its digits (which are not just $0/1$) and add the multiplicand times the digits times a power of the base, $10$ (this is just appending zeroes).

$$73_d=7\cdot10^1+3\cdot10^0$$

and

$$(7\cdot10^1+3\cdot10^0)\cdot217=(7\cdot10^1\cdot217)+(3\cdot10^0\cdot217).$$

One may generalize by expressing the multiplier in any other base, but there is no benefit.