Programming Java Assignment.

Russian Peasant Method.

Consider a nonorthodox algorithm for multiplying two positive integers called multiplication a la russe or the Russian peasant method.

Let n and m be positive integers whose product we want to compute, and let is measure the instance size by the value of n. Now, if n is even, an instance of half the size has to deal with n/2, and we have an obvious formula relating the solution to the problems larger instance to the solution to the smaller one:

n * m = (n / 2 ) * 2 * m

If n is odd, we need only a slight adjustment of this formula:

n * m = (( n 1 ) / 2 ) * 2 * m + m.

Using this formula and the trivial case of 1 * m = m to stop, we can compute product n * m either recursively or iteratively. An example of computing 50 * 65 with this algorithm is given below. Note that all the extra addends shown in parentheses in the figure below are in the rows that have odd values in the first column. Therefore, we can find the product by simply adding all the elements in the m column that has an odd number in the n column.

Also note that the algorithm involves the simple operations of halving, doubling, and adding a feature that might be attractive, for example, to those who do not want to memorize the table of multiplication. It is this feature of the algorithm that most probably made it attractive to Russian peasant, who, according to Western visitors, used it widely in the nineteen century and for whom method is named. It also leads to very fast hardware implementation since doubling and halving of binary numbers be can be performed using shifts, which are among the most basic operations at the machine level.

n m

50 65

25 130

12 260 ( + 130 )

6 520

3 1040

1 2080 ( + 1040 )

2080 + ( 130 + 1040 ) = 3250

Use an appropriate loop.

a) Write and debug a Java program for this algorithm. It should be able to produce the following screen display, as above table.

b) As an option, perform input validation for the other input entities: