ロシア農民の掛け算

いわゆる「ロシア農民の掛け算」をJavaScriptで実装してみました。

動作原理は、ネット上にもいろいろ詳しい解説がありますが、下記のような感じです。

例題：34227 * 36070
片方を２倍、片方を半分にする。
34227 * 36070
= (34227 * 2) * (36070 / 2)
= 68454 * 18035
2.を繰り返していくのが基本だが、半分にする方の数が奇数だった場合はそのままでは半分にならないので、以下のように変形する。
68454 * 18035
= 68454 * (1 + 18034)
= 68454 + 68454 * 18034
= 68454 + ((68454 * 2) * (18034 / 2))
= 68454 + 136908 * 9017
136908 * 9017 の部分を3.と同様の手順で変形する。
136908 * 9017
= 136908 + 136908 * 9016
= 136908 + 273816 * 4508
今度は 273816 * 4508 を2.と同様の手順で変形する。
273816 * 4508
= (273816 * 2) * (4508 / 2)
= 547632 * 2254
半分にする方の数が 1 になるまで、2. 3. を繰り返す。
変形後の式は足し算のみになっているので、足し算を実行する。
68454 + 136908 + 1095264 + 2190528 + 4381056 + 35048448 + 70096896 + 1121550336
= 1234567890

ソース

RussianPeasant.html

<html>
<head>
  <meta http-equiv="Content-Type" context="text/html; charset=UTF-8" />
  <meta charset="UTF-8" />
  <title>ロシア農民の掛け算。</title>
<script>

function doCalc() {
    var txtN1 = document.getElementById("txtN1");
    var txtN2 = document.getElementById("txtN2");
    var n1, n2, strResult;
    var vWork = [];
    var vOut = [];

    n1 = parseInt(txtN1.value, 10);
    n2 = parseInt(txtN2.value, 10);

    vOut.push("  " + n1 + " * " + n2);

    while (1) {
        if (n2 <= 1) { break; }

        if (n2 % 2 == 0) {
            n2 = n2 / 2;
        } else {
            strResult = "= ";
            for (let i = 0; i < vWork.length; i++) {
                strResult += vWork[i] + " + ";
            }
            vOut.push(strResult + n1 + " + " + n1 + " * " + (n2 - 1));
            n2 = (n2 - 1) / 2;
            vWork.push(n1);
        }

        n1 = (n1 * 2);

        strResult = "= ";
        for (let i = 0; i < vWork.length; i++) {
            strResult += vWork[i] + " + ";
        }

        if (n2 == 1) {
            vOut.push(strResult + n1 + " * " + n2);
            vOut.push(strResult + n1);
        } else {
            vOut.push(strResult + n1 + " * " + n2);
        }
    }

    var nResult = 0;
    for (let i = 0; i < vWork.length; i++) {
        nResult += vWork[i];
    }
    nResult += n1;
    vOut.push("= " + nResult);

    document.getElementById("result").innerHTML = vOut.join("\n");
}

</script>
</head>
<body>

<h2>ロシア農民の掛け算。</h2>
5桁 * 5桁 まで<br />
<input type="text" id="txtN1" value="34227" maxlength="5" size="7" oninput="value = value.replace(/[^0-9]+/i,'');" /> ×
<input type="text" id="txtN2" value="36070" maxlength="5" size="7" oninput="value = value.replace(/[^0-9]+/i,'');" />
<input type="button" value="計算" onclick="doCalc()" /><br />
<br />

<textarea id="result" rows="50" col="20" style="width:700px;height:400px;">
</textarea>

</body>
</html>

ロシア農民の掛け算をJavaScriptでやってみた

ロシア農民の掛け算

ソース