PHP 實作俄羅斯農民乘法演算法

演算法簡介

俄羅斯農民乘法（Russian Peasant Multiplication），又稱古埃及乘法，是一種不需要背誦乘法表、僅靠「減半、加倍、加法」即可完成兩數相乘的古老演算法。原理基於二進位分解與分配律。

演算法步驟示例：35 × 72

結果： 72 + 144 + 2304 = 2520 （驗證：35 × 72 = 2520 ✓）

PHP 遞迴實作（位元運算優化版）

<?php
/**
 * 俄羅斯農民乘法 - 遞迴實作
 * 
 * @param int $m 被乘數（將不斷左移/加倍）
 * @param int $n 乘數（將不斷右移/減半）
 * @param int $acc 累加器（內部使用）
 * @return int 乘積
 */
function russianMultiply($m, $n, $acc = 0) {
    // 1. 若乘數最低位為 1（奇數），累加被乘數
    if ($n & 1) {
        $acc += $m;
    }
    
    // 2. 被乘數左移 1 位（×2），乘數右移 1 位（÷2，捨去小數）
    $m <<= 1;
    $n >>= 1;
    
    // 3. 遞迴終止條件：乘數歸零
    return $n ? russianMultiply($m, $n, $acc) : $acc;
}

// 測試
echo "7 × 8 = " . russianMultiply(7, 8) . "\n";    // 56
echo "35 × 72 = " . russianMultiply(35, 72) . "\n"; // 2520
echo "123 × 456 = " . russianMultiply(123, 456) . "\n"; // 56088
?>

非遞迴迭代版本（避免堆疊溢位）

<?php
function russianMultiplyIterative($a, $b) {
    $result = 0;
    
    while ($b > 0) {
        // 若 b 為奇數，累加 a
        if ($b & 1) {
            $result += $a;
        }
        // a 加倍，b 減半
        $a <<= 1;
        $b >>= 1;
    }
    
    return $result;
}

// 效能測試
$start = microtime(true);
for ($i = 0; $i < 100000; $i++) {
    russianMultiplyIterative(12345, 6789);
}
echo "迭代版 10萬次耗時: " . (microtime(true) - $start) . " 秒\n";

$start = microtime(true);
for ($i = 0; $i < 100000; $i++) {
    russianMultiply(12345, 6789);
}
echo "遞迴版 10萬次耗時: " . (microtime(true) - $start) . " 秒\n";
?>

原理深度解析：二進位分解視角

以 13 × 11 為例：

11 (十進位) = 1011 (二進位) = 1×2³ + 0×2² + 1×2¹ + 1×2⁰
            = 8 + 0 + 2 + 1

13 × 11 = 13 × (8 + 2 + 1)
        = 13×8 + 13×2 + 13×1
        = 104 + 26 + 13
        = 143

演算法過程中：

• $n & 1 檢查當前最低位是否為 1（對應二進位某位是否為 1）
• $m <<= 1 對應 13 × 2^k 的逐級加倍
• $n >>= 1 對應逐位檢查二進位各位

效能與適用性

擴展：大整數乘法（配合 BCMath）

<?php
function russianMultiplyBC($a, $b) {
    $result = '0';
    $a = (string)$a;
    $b = (string)$b;
    
    while (bccomp($b, '0') > 0) {
        // 判斷奇數：最後一位數字為 1,3,5,7,9
        $lastDigit = substr($b, -1);
        if (in_array($lastDigit, ['1','3','5','7','9'])) {
            $result = bcadd($result, $a);
        }
        $a = bcmul($a, '2');
        $b = bcdiv($b, '2', 0); // 整數除法
    }
    
    return $result;
}

// 測試大整數
echo russianMultiplyBC('12345678901234567890', '98765432109876543210') . "\n";
// 輸出: 1219326311370217952237463801111263526900
?>

俄羅斯農民乘法雖非實務高效能選擇，但展示了演算法思維與位元運算的優雅結合，是理解電腦乘法原理、二進位運算與遞迴設計的優秀教學案例。