Use recursion to solve theRussian Peasant Multiplication problem defined on pages 153-154 of the text book. Hints(1) n/2 = n >> 1and (2) 2m = m

//------------------------------------------------------------

// Quiz over Chapter #4, Question #12

// Quiz4Question12.c

//------------------------------------------------------------

#include

#include

#include

//------------------------------------------------------------

int main()

//------------------------------------------------------------

{

int RussianPeasantMethod(const int n,const int m);

int n,m;

printf("n m? ");

while ( scanf("%d%d",&n,&m) != EOF )

{

printf("%d*%d = %d ",n,m,RussianPeasantMethod(n,m));

printf(" n m? ");

}

system("PAUSE");

return( 0 );

}

Russian Peasant Multiplication Now we consider a nonorthodox algorithm for multiplying two positive integers called multiplication la russe or the Russian peasant method. Let n and m be positive integers whose product we want to compute, and let us 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 problem's larger instance to the solution to the smaller one 1l If n is odd, we need only a slight adjustment of this formula 2m + m Using these formulas and the trivial case of 1 mto stop, we can compute product n m either recursively or iteratively. An example of computing 50 65 with this algorithm is given in Figure 4.11. Note that all the extra addends shown in parentheses in Figure 4.11a 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 have an odd number in the n column (Figure 4.11b) Also note that the algorithm involves just the simple operations of halving, doubling, and adding-a feature that might be attractive, for example, to those Decrease-and-Conquer 50 25 12 65 50 25 12 65 130 260 520 130 130 260 (+130) 520 3 1040 3 1040 1040 2080 2080 3250 1 2080 (+1040) 2080 +4130 + 1040) = 3250 FIGURE 4.11 Computing 50 65 by the Russian peasant method who do not want to memorize the table of multiplications. It is this feature of the algorithm that most probably made it attractive to Russian peasants who, accord ing to Western visitors, used it widely in the nineteenth century and for whom the method is named. (In fact, the method was known to Egyptian mathematicians as early as 1650 .. [Cha98, p. 16].) It also leads to very fast hardware implementa- tion since doubling and halving of binary numbers can be performed using shifts, which are among the most basic operations at the machine level