The Vault : Problem # 23

Problem # 23 : Russian Peasants

The Russian peasants had an interesting way of doing multiplication of (not very large) integers. This method can be illustrated by the following example :

If 17 and 19 are to be multiplied they are put at the top of two columns

The number at the top of one column is successively divided by 2 (integer division) while the number in the other column in successively multiplied by 2. The results of these operations are written one below the other in their respective columns. This process is repeated till the number in column containing the division reaches 1. For the above two numbers the process will be as follows :

17	19
8	38
4	76
2	152
1	304

At this stage all the numbers in the right-hand column are struck off where the corresponding number on the left-hand column is even :

17	19
8	38	struck off
4	76	struck off
2	152	struck off
1	304

The remaining numbers on the right-hand side are added i.e 19+304=323 which is the product of the two original numbers.

Write a procedure MULTIPLY(M N) which multiplies M and N using this method and prints each step on a cleared screen. (The values of M and N will not exceed 99)

Sample Output
MULTIPLY(79 46) should generate the following output :

79	46
39	92
19	184
9	368
4	736	struck off
2	1472	struck off
1	2944
	---------------
	3634
	---------------

(Back to problems at The Vault )

LinkExchange Member