โปรแกรม C++ ใช้ Russian Peasant Multiplication

Russian Peasant algorithm สำหรับคูณสองจำนวน เป็นอัลกอริทึมที่รวดเร็วสำหรับคำนวณการคูณของตัวเลขยาวสองตัว

อัลกอริทึม

Begin
    Russianpeasant(num1, num2)
    Int result = 0
    while (num2 > 0)
        ถ้า (num2 and 1)
            result = result + n;
        num1 = num1 left shift 1;
        num2 = num2 right shift 1;
    return result
End

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

unsigned int russianPeasant(unsigned int n, unsigned int m) {
    int result = 0;
    while (m > 0) {
        if (m & 1)
            result = result + n;
        n = n << 1; // left shift 1
        m = m >> 1; // right shift 1
    }
    return result;
}

int main() {
    cout << russianPeasant(10, 20) << endl;
    cout << russianPeasant(7, 6) << endl;
    return 0;
}

ผลลัพธ์

200
42