Chương trình C++ triển khai thuật toán nhân dân روسيا (Russian Peasant Multiplication)

Thuật toán nhân dân Russia (Russian Peasant) để nhân hai số. Đây là thuật toán nhanh để tính phép nhân của hai số lớn.

Thuật toán

Bắt đầu
    Russianpeasant(num1, num2)
    Int result = 0
    Khi (num2 > 0)
        Nếu (num2 và 1)
            result = result + n;
        num1 = num1 dịch trái 1;
        num2 = num2 dịch phải 1;
    Trả về result
Kết thúc

Mã ví dụ

#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; 
        m = m >> 1; 
    } 
    return result; 
} 

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

Kết quả

200 
42