Can you please do this using c++? Q3 Russian peasant multiplication . Russian pe
ID: 3915235 • Letter: C
Question
Can you please do this using c++?
Q3 Russian peasant multiplication . Russian peasant multiplication is an algorithm to multiply two (positive) integers. . It is actually an old algorithm. There is evidence it was known by the ancient Egyptians. . It is simplest to explain with an example. Suppose we wish to multiply 89 x 21. 1. Let a 89 and b-# 21. Forn a table of three columnis of numbers as follows. 21 42 84 168 336 672 1344 21 168 336 1344 1869 (sum) 2. At each step, if a is odd, we copy the value of b into the third column. 3. Then we divide a by 2 (integer division) and multiply b by 2. 4. We stop when the value of a reaches 0. h mothe unbhers in the third column. . Hence the algorithm breaks down the multiplication of two (possibly large) numbers into a set of additions and integer multiplications and divisions by 2. 1. Integer multiplication and division by 2 are easy operations in binary. 2. Integer multiplication by 2 is a left shift of the binary digits of a number. 3. Integer division by 2 is a right shift of the binary digits of a number (and loss of the "least significant bit") 4. Addition is also a simpler operation than multiplication, in general. Implement a function for Russian peasant multiplication of two positive integers. int RPM(int a, int b); 1. Declare and initialize a telliporary variable int sum " 0. 2. Begin a loop. (a) If a is odd then increment sum sum b (b) Perform integer division a - a/2 and integer multipliation b (c) Repeat the loop. Stop when ? = 0. b*2. 3. Return the value of sum. . Set a and b to the first and last four digits of your student id. . If id -23054611, then a-2305 and ?n, 4611, Use your function to multiply a x b.Explanation / Answer
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
//Code
#include<iostream>
using namespace std;
//method to multiply two numbers using Russian Peasant Multiplication
int RPM(int a, int b){
//defining temporary variable sum
int sum=0;
//looping until a is greater than 0
while(a>0){
//if a is odd
if(a%2!=0){
//adding b to sum
sum=sum+b;
}
//performing integer division a/2
a=a/2; //as a is an int, a/2 will be automatically casted to int
//performing integer multiplication b*2
b=b*2;//as b is an int, b*2 will be automatically casted to int
}
return sum; //returning sum
}
int main(){
//testing the above method
cout<<"89*21 = "<<RPM(89,21)<<endl;
cout<<"1234*5678 = "<<RPM(1234,5678)<<endl;
cout<<"11111111*9 = "<<RPM(11111111,9)<<endl;
}
/*OUTPUT*/
89*21 = 1869
1234*5678 = 7006652
11111111*9 = 99999999