0

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?

enter image description here

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
SARTHAK GUPTA
  • 1,310
  • 9
  • 24
  • Look up the [wiki](https://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication#Russian_peasant_multiplication). – A.Γ. Mar 03 '20 at 20:48
  • a.k.a. [Russian peasant multiplication](https://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication#Russian_peasant_multiplication), on which there are many prior questions here (so this is likely a dupe ... indeed, see above) – Bill Dubuque Mar 03 '20 at 21:07
  • @BillDubuque What about comparison with other methods of multiplication? – SARTHAK GUPTA Mar 03 '20 at 21:30
  • It computes $\,f(a,b,c) = ab+c\,$ (for integers $\,a,b,c,\ a\ge 0)\,$ by the following recursion $$f(a,b,c)\, :=\, \begin{cases}\qquad\qquad\qquad\quad\! c\,\ \ \ \ \ \ \ \ {\rm if}\ \ a=0\\[.3em] f(\ \ \ \ a/2,\ \ \ \ \ 2b,\ c)\ \ \ \ \ \ \ {\rm if}\ \ a\ \,{\rm is\ even}\\[.3em] f((a\!-\!1)/2,\,2b,\ c\!+\!b)\ \ {\rm if}\ \ a\ \,{\rm is\ odd}\\ \end{cases}\qquad$$ – Bill Dubuque Mar 03 '20 at 21:44
  • It's clearly correct, e.g. $\,((a\!-\!1)/2)(2b)\!+\!c\!+\!b = (a\!-\!1)b\!+\!c\!+\!b = ab+c,\,$ and the recursive calls have *decreasing* $(\ge 0)$ first argument (multiplier), so it eventually reaches $ 0$ (by $\Bbb N$ well-ordered). – Bill Dubuque Mar 03 '20 at 21:44
  • 1
    @SARTHAKGUPTA You're supposed to ask only one question per post. If you have further questions on this then please post them separately (but please first search here on "russian peasant" etc to see if they are already answered). – Bill Dubuque Mar 03 '20 at 21:46

2 Answers2

0

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*}$

vonbrand
  • 27,174
  • 6
  • 39
  • 74
0

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.