Russian Peasant Multiplication Algorithm

Question

For university, we have just started to learn C++ as a language, and one of our challenges to do in our spare time is to write an algorithm for 'Peasant multiplication'. In the challenge, we have been told that we cannot use the multiplication operator *.

My code for it is as follows.

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <limits>
using namespace std;
vector<int> half(float numberToHalf) {
 vector<int> steps;
 while (numberToHalf != 1) {
 steps.push_back(numberToHalf);
 numberToHalf = floorf(numberToHalf / 2);
 }
 steps.push_back(1);
 return steps;
}
vector<int> repeatedDouble(int number, int limit) {
 vector<int> doubleList;
 for (int i = 0; i < limit; i++)
 { 
 doubleList.push_back(number);
 number += number;
 } 
 return doubleList;
}
int adding(vector<int> halfList, vector<int> doubleList) {
 int total = 0;
 for (int i = 0; i < halfList.size(); i++) {
 if (halfList[i] % 2 != 0) {
 total += doubleList[i];
 }
 }
 return total;
}
int verify(string timeRound) {
 bool roundAgain = true;
 int number;
 do {
 cout << "Enter the " << timeRound << " number: " << endl;
 cin >> number;
 if(cin.good() && 0 < number) { //if number entered is positive and an integer
 roundAgain = false;
 }else {
 //Make cin ready to take another input 
 cin.clear();
 cin.ignore(numeric_limits<streamsize>::max(),'\n'); //Snippet taken from https://stackoverflow.com/questions/16934183/integer-validation-for-input
 cout << "A valid input is a POSITIVE, whole, number. No letters, words, or negatives" << endl;
 }
 } while (roundAgain);
 return number;
}
int main() {
 int num1 = verify("First");
 int num2 = verify("Second");
 vector<int> halved = half(num1);
 vector<int> doubled = repeatedDouble(num2, halved.size());
 cout << "The result is: " << adding(halved, doubled);
}

Any help in optimising the code to make it look and run even better would be appreciated! Also, if any of you could give some tips for robustness or similar that would be great too!

I am completely new to C++ so any tricks and tips from experienced coders would be amazing!

Answer 1

It looks to me that you're being too literal. When trying to convert an analog process to code it's easy to fall into that trap.

Presently you're using 2 loops to make 2 lists. This is unnecessary. You can do everything including calculate the answer in one loop.

You're also not checking for which number is the lesser one and which is the greater one. This is integral to the base algorithm, that you're trying to emulate.

A simplified version could look something like this:

int PeasantMultiply(int num1, int num2)
{
 auto pair = std::minmax(num1, num2);
 int min = pair.first;
 int max = pair.second;
 int total = 0;
 if (min != 0)
 {
 do
 {
 if (min % 2 == 1)
 {
 total += max;
 }
 min /= 2;
 max += max;
 } while (min > 0);
 }
 return total;
}

After looking at this code again, I came upon an optimization. Instead of using the modulus operator(%), I could accomplish the same thing with and extra int variable and use subtraction instead:

int PeasantMultiply(int num1, int num2)
{
 auto pair = std::minmax(num1, num2);
 int oldMin = pair.first;
 int max = pair.second;
 int total = 0;
 int newMin = 0;
 if (oldMin != 0)
 {
 do
 {
 newMin = oldMin / 2;
 if (oldMin - newMin != newMin)
 {
 total += max;
 }
 oldMin = newMin;
 max += max;
 } while (oldMin > 0);
 }
 return total;
}

In my tests this saves about 10% in time.

• Tom Scott: Thanks for this! Would you be able to tell me what minmax() does?
• user33306: @TomScott - It returns a pair. pair::first contains the lesser number and pair::second is the greater number. It is in the algorithm header.
• davidbear: @tinstaafl, I believe this code is in error, the max % 2 == 1 should not be in the if statement. Currently, PeasantMultiply(5,4) yields 25.
• user33306: It's corrected now