ロシア農民の掛け算
いわゆる「ロシア農民の掛け算」を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>