俄羅斯農民乘法(Russian Peasant Multiplication)是一種古老的乘法算法,僅使用加法、除以 2、乘以 2 運算即可完成兩數相乘。本文介紹其原理並提供 PHP 遞歸實現。
以 35 × 72 為例:
| 左列(不斷除 2,取整) | 右列(不斷乘 2) |
|---|---|
| 35 | 72 |
| 17 | 144 |
| 8 | 288 |
| 4 | 576 |
| 2 | 1152 |
| 1 | 2304 |
規則:左列為奇數時,將右列對應數值累加。
72 + 144 + 2304 = 2520 = 35 × 72
<?php
function russian($m, $n, $res = 0) {
// 若 n 為奇數(最低位為 1),累加 m
(1 == ($n & 1)) && $res += $m;
// m 左移 1 位(乘 2),n 右移 1 位(除 2 取整)
$m = $m << 1;
$n = $n >> 1;
// 遞歸直到 n 為 0
return $n ? russian($m, $n, $res) : $res;
}
echo russian(7, 8); // 輸出 56
?>
$n & 1:判斷最低位是否為 1(即奇數)。$m << 1:左移 1 位等價於乘 2。$n >> 1:右移 1 位等價於整除 2。$n == 0。<?php
function russian_iterative($m, $n) {
$res = 0;
while ($n > 0) {
if ($n & 1) $res += $m;
$m <<= 1;
$n >>= 1;
}
return $res;
}
?>
教學演示、嵌入式系統無乘法指令環境、大整數乘法底層實現參考等。