C++でロシアン・ピーザント法（ロシア農民の掛け算）を実装するプログラム

ロシアン・ピーザント法（Russian Peasant Algorithm、通称「ロシア農民の掛け算」）は、2つの数値の積を高速に計算するためのアルゴリズムです。大きな数同士の乗算でも、シフト演算と加算だけで効率よく処理できる点が大きな特徴です。

アルゴリズム

基本的な流れは以下のとおりです。

開始
    RussianPeasant(num1, num2)
    result = 0
    while (num2 > 0)
        if (num2 の最下位ビットが 1)
            result = result + num1
        num1 を左に1ビットシフト（2倍）
        num2 を右に1ビットシフト（半分）
    return result
終了

仕組みのポイントを整理すると次のようになります。

• 片方の数（m）が0になるまでループを繰り返します。
• m の最下位ビットが1のときだけ、その時点の n を結果に加算します。
• n は毎回2倍（左シフト）、m は毎回半分（右シフト）していくことで、通常の筆算と同じ原理で積を求められます。

サンプルコード

実際にC++で実装した例がこちらです。

#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;
}

出力結果

200
42

このプログラムでは russianPeasant(10, 20) の結果として 200、russianPeasant(7, 6) の結果として 42 が出力されます。乗算演算子を使わずに正しい積が求まっていることがわかります。