Russian Peasant Multiplication Algorithm In C++

Introduction:

The technique of Russian Peasant Multiplication, alternatively referred to as the Egyptian Multiplication method, is a historical approach for multiplying two numerical values. This method is based on the principles of halving and doubling, which enables quicker calculations by breaking down the multiplication process into smaller, manageable steps. By iteratively reducing one of the numbers by half and incrementally accumulating the outcome under certain criteria, this algorithm proves to be effective for manual computations.

How does it works?

The fundamental concept of the Russian Peasant Multiplication technique involves repetitively dividing one number by 2 (halving) and multiplying the other number by 2 (doubling). When the halved number is odd, the doubled number is included in the final result. Conversely, if the halved number is even, the doubled number is disregarded. This procedure persists until the initial number reaches 1.

Approach 1: Simple Approach

Implementation:

#include <iostream>
using namespace std;
int russianPeasantMultiplication(int a, int b) {
    int result = 0;  // This will store the final product
    while (a > 0) {
        // If 'a' is odd, add 'b' to result
        if (a % 2 != 0) {
            result += b;
        }  
        // Halve 'a' and double 'b'
        a /= 2;
        b *= 2;
    }
    return result;
}
int main() {
    int a = 18;
    int b = 25;
    cout << "The product of " << a << " and " << b << " is: "
         << russianPeasantMultiplication(a, b) << endl;
    return 0;
}

Output:

The product of 18 and 25 is: 450

Explanation:

• ✅ Initialization: When the algorithm starts, two numbers are provided for multiplication. One number (a) will undergo the halving process, while the other (b) will be doubled repeatedly. A third variable, the result, is initialized to zero, which will store the running total as the algorithm progresses.
• ✅ Main Loop Execution: The multiplication process revolves around a loop that continues as long as a remains greater than zero. Each iteration of the loop performs the following tasks: Odd Check on a: At the beginning of each loop iteration, the algorithm checks whether a is odd . This is important because if a is strange, the current value of b needs to be added to the running total (result). This step accounts for the fact that when a is odd, the multiplication cannot be neatly split without a remainder. Thus, the doubled value of b represents this leftover portion that needs to be accumulated. Halving a: Next, a is halved, which means dividing it by 2. Halving a can be visualized as reducing the problem by removing one bit of precision in a binary system. Since multiplication can be represented by shifting bits in binary, halving minimises the size of the multiplication problem progressively. If the number is odd, the fractional part is discarded (since we only care about integers). Doubling b: Simultaneously, b is doubled during each iteration. This doubling process compensates for halving a because, while a is being reduced, b is being inflated to ensure that the product of the two numbers remains consistent. Doubling b can be thought of as multiplying by 2 in each iteration.
• ✅ Running Total (Result): As mentioned earlier, if a is odd in any iteration, the current value of b is added to the result. This accumulation is crucial for ensuring that the final answer includes all parts of the multiplication that cannot be handled purely by the halving process (i.e., when a is odd). If a is even, no addition happens, and the loop moves to the next iteration.
• ✅ Loop Continuation: The loop repeats these steps-halving a, doubling b, checking if a is odd, and updating the result-until a is reduced to zero or one. If a is one at the final step, the value of b is added to the result since the multiplication is now reduced to its final form.
• ✅ Final Output: When the loop completes, the result variable holds the product of the original values of a and b. The reason this works is that the process effectively breaks the multiplication into manageable chunks by halving and doubling, and it ensures that any leftover parts (from odd values of a) are accounted for by adding the corresponding value of b.
• ✅ Odd Check on a: At the beginning of each loop iteration, the algorithm checks whether a is odd . This is important because if a is strange, the current value of b needs to be added to the running total (result). This step accounts for the fact that when a is odd, the multiplication cannot be neatly split without a remainder. Thus, the doubled value of b represents this leftover portion that needs to be accumulated.
• ✅ Halving a: Next, a is halved, which means dividing it by 2. Halving a can be visualized as reducing the problem by removing one bit of precision in a binary system. Since multiplication can be represented by shifting bits in binary, halving minimises the size of the multiplication problem progressively. If the number is odd, the fractional part is discarded (since we only care about integers).
• ✅ Doubling b: Simultaneously, b is doubled during each iteration. This doubling process compensates for halving a because, while a is being reduced, b is being inflated to ensure that the product of the two numbers remains consistent. Doubling b can be thought of as multiplying by 2 in each iteration.

Complexity Analysis:

Time Complexity:

Halving and Doubling:

Throughout each cycle, the procedure divides a by half and multiplies b by two. Reducing a by half in each step significantly decreases the size of the problem as each division by 2 decreases a by a factor of 2.

The quantity of times you can divide a number a by half before reaching zero is directly related to the logarithm of a, precisely O(log a).

Odd Verification and Summation:

Determining if a is an odd number is an operation that runs in constant time, denoted as O(1).

Furthermore, the addition of b to the total sum also falls under constant-time complexity, represented as O(1).

Therefore, the algorithm executes a consistent quantity of operations in every cycle, with the number of cycles scaling in relation to the logarithm of a. Consequently, the total time complexity is O(log a).

Space Complexity:

The algorithm of Russian Peasant Multiplication utilizes minimal additional variables like outcome, and temporary duplicates of a and b. These variables consume consistent space.

• ✅ There is no dependency on additional arrays or dynamic data structures.
• ✅ The memory needed remains constant regardless of the magnitude of the input values.

Therefore, the spatial complexity remains O(1) (constant space) irrespective of the magnitude of the input values.

Approach 2: Using the Karatsuba Algorithm

The Karatsuba Algorithm decreases the time complexity of the multiplication process by decomposing larger numbers into smaller segments, thus requiring fewer multiplication operations. It is based on the concept that the multiplication of two numbers can be performed by breaking down the numbers into smaller components, multiplying these components, and then merging the outcomes. This algorithm offers a more efficient time complexity compared to traditional multiplication, where the time complexity is O(n²) for two n-digit numbers.

Implementation:

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
// Helper function to make two numbers of equal length by padding zeros in front
string addZeros(string str, int num) {
    for (int i = 0; i < num; i++) {
        str = "0" + str;
    }
    return str;
}
// Helper function to add two numeric strings
string addStrings(string num1, string num2) {
    string result = "";
    int carry = 0, sum;
    int length1 = num1.size(), length2 = num2.size();
    if (length1 < length2)
        num1 = addZeros(num1, length2 - length1);
    else
        num2 = addZeros(num2, length1 - length2);
    for (int i = num1.size() - 1; i >= 0; i--) {
        sum = (num1[i] - '0') + (num2[i] - '0') + carry;
        carry = sum / 10;
        result = char(sum % 10 + '0') + result;
    }
    if (carry) result = "1" + result;
    return result;
}
// Helper function to subtract two numeric strings
string subtractStrings(string num1, string num2) {
    string result = "";
    int carry = 0, sub;
    int length1 = num1.size(), length2 = num2.size();
    if (length1 < length2)
        num1 = addZeros(num1, length2 - length1);
    else
        num2 = addZeros(num2, length1 - length2);
    for (int i = num1.size() - 1; i >= 0; i--) {
        sub = (num1[i] - '0') - (num2[i] - '0') - carry;
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        } else {
            carry = 0;
        }
        result = char(sub + '0') + result;
    }
    // Remove leading zeros
    while (result.size() > 1 && result[0] == '0') {
        result.erase(0, 1);
    }
    return result;
}
// Multiply two numeric strings using Karatsuba algorithm
string karatsubaMultiply(string x, string y) {
    int n = max(x.size(), y.size());
    // Base case
    if (n == 1)
        return to_string((x[0] - '0') * (y[0] - '0'));
    // Make the lengths of x and y equal by adding zeros in front
    if (x.size() < n) x = addZeros(x, n - x.size());
    if (y.size() < n) y = addZeros(y, n - y.size());
    int m = n / 2;
    // Split x and y
    string x1 = x.substr(0, n - m);
    string x0 = x.substr(n - m);
    string y1 = y.substr(0, n - m);
    string y0 = y.substr(n - m);
    // Recursive calls
    string z2 = karatsubaMultiply(x1, y1);
    string z0 = karatsubaMultiply(x0, y0);
    string z1 = karatsubaMultiply(addStrings(x1, x0), addStrings(y1, y0));
    // z1 = z1 - z2 - z0
    z1 = subtractStrings(subtractStrings(z1, z2), z0);
    // Combine the three results
    for (int i = 0; i < 2 * m; i++) z2 += "0";  // z2 * 10^(2*m)
    for (int i = 0; i < m; i++) z1 += "0";     // z1 * 10^m
    return addStrings(addStrings(z2, z1), z0);
}
int main() {
    string x = "1234";
    string y = "5678";
    cout << "Product of " << x << " and " << y << " is: " 
         << karatsubaMultiply(x, y) << endl;
    return 0;
}

Output:

Product of 1234 and 5678 is: 7006652

Explanation:

• ✅ Understanding the Problem: We are trying to multiply two large numbers. Instead of using traditional long multiplication, which takes time proportional to the square of the number of digits, the Karatsuba algorithm breaks the problem into smaller parts and solves it more efficiently using a divide-and-conquer approach.
• ✅ Breaking Down the Numbers: The algorithm works by splitting both numbers into two parts. If the numbers are large (let's say four digits each), they are split into higher and lower halves. For example: For x = 1234, split it into x1 = 12 (higher part) and x0 = 34 (lower part). For y = 5678, split it into y1 = 56 (higher part) and y0 = 78 (lower part).
• ✅ For x = 1234, split it into x1 = 12 (higher part) and x0 = 34 (lower part).
• ✅ For y = 5678, split it into y1 = 56 (higher part) and y0 = 78 (lower part).

When dividing the numbers individually, we can represent the multiplication issue as:

x * y = (x1 * 10^m + x0) * (y1 * 10^m + y0)

Where m represents the quantity of digits in the lower segment (e.g., m = 2 in this instance).

1. Three Primary Multiplications:

To compute the product of two numbers using this formula, we need three multiplications:

• ✅ z2: This is the product of the higher parts (x1 * y1).
• ✅ z0: This is the product of the lower parts (x0 * y0).
• ✅ z1: This is the product of the sum of the parts:
• ✅ First, compute (x1 + x0) and (y1 + y0).
• ✅ Then multiply these sums together.
• ✅ Subtract the previously calculated z2 and z0 from this result.

This provides us with the central element, which is essential for merging the three outcomes efficiently.

1. Recursion Calls:

Each of the three multiplications (z2, z0, and z1) entails using lesser values compared to the initial issue. Should these values remain noteworthy, the procedure will invoke itself in a recursive manner, continuously breaking down the numbers until they are sufficiently reduced for direct multiplication.

This iterative process contributes to the algorithm's effectiveness by decomposing extensive multiplications into smaller tasks, consequently diminishing the overall time complexity.

1. Merging Outcomes:

Once the three parts (z2, z0, and z1) are computed, the algorithm combines them to get the final product. The combination works like this:

• ✅ z2 is multiplied by 10^(2m) (shifting it to the left by 2m digits).
• ✅ z1 is multiplied by 10^m (shifting it to the left by m digits).
• ✅ Finally, all three terms (z2, z1, and z0) are added together to form the final product.

1. Helper Functions:

Since the numbers are handled as strings (to manage large values), the algorithm includes helper functions for:

• ✅ Padding zeros: This ensures both numbers have the same number of digits when performing operations.
• ✅ Adding strings: To add two large numbers stored as strings.
• ✅ Subtracting strings: To subtract one large string number from another.

These auxiliary functions are essential for handling operations involving significant numerical values to prevent exceeding the limits of the data type.

1. Initial Condition:

The process of recursion terminates once the values become sufficiently small to undergo direct multiplication (specifically, single-digit numbers). At this point, the program executes the fundamental multiplication operation and provides the outcome.

1. Last Stage:

After the iterative calls and the trio of multiplications (z2, z1, and z0), the outcomes are merged to produce the ultimate solution. This cycle of segmenting, iteratively multiplying, and merging persists until all the recursive calls are resolved.

Complexity Analysis:

Time Complexity:

Recursion: The Karatsuba method divides numbers into two halves repeatedly until they reach a size suitable for direct multiplication. With every recursive invocation, the size of the input is reduced by half. This algorithm executes three multiplications during each recursion level, deviating from the standard four multiplications.

Logarithmic Depth: When the input consists of n digits, the recursive depth equals log₂(n) as the input size gets divided by 2 with each iteration.

Multiplication Expense: In every iteration of recursion, three multiplication operations are executed on values that are halved in size, and this pattern persists throughout the recursion tree. The expense associated with aggregating the outcomes (via addition and subtraction) remains proportional at each level.

Overall Time Complexity: The complete time complexity is represented as O(n^log₂3), which can be simplified to roughly O(n^1.585). This offers a substantial improvement compared to the O(n²) time complexity associated with standard multiplication methods when dealing with large numbers.

Space Complexity:

Recursive Stack: As the algorithm employs recursion, the space needed by the recursion stack is contingent on the recursion's depth. The depth of recursion is log₂(n) as the input size is divided by two at every recursive iteration.

Temporary Memory Allocation: Within every iteration, memory allocation is required to store temporary values (such as z2, z1, and z0), along with the outcomes of arithmetic operations.

Overall Memory Complexity: The memory complexity amounts to O(n) as it is necessitated by the storage needed for recursive function invocations and holding temporary outcomes while executing addition and subtraction processes.