PHP 實現俄羅斯乘法法（Russian Peasant Multiplication）遞迴演算法

PHP 實現俄羅斯乘法法（Russian Peasant Multiplication）遞迴演算法

演算法原理

俄羅斯乘法又稱古埃及乘法，利用二進制分解原理計算兩數相乘：

1. 將兩數分別寫在左右兩欄。
2. 左欄連續除以 2（捨去餘數），右欄連續乘以 2，直到左欄變為 1。
3. 將左欄為奇數的行對應的右欄數值累加，即為乘積。

範例：35 × 72

左欄  右欄
35    72   ← 奇數，累加 72
17    144  ← 奇數，累加 144
8     288  ← 偶數，忽略
4     576  ← 忽略
2     1152 ← 忽略
1     2304 ← 奇數，累加 2304
總和：72 + 144 + 2304 = 2520

PHP 遞迴實作

<?php
function russian($m, $n, $res = 0) {
    // $n 最低位為 1（奇數）時累加 $m
    (1 == ($n & 1)) && $res += $m;
    // 左移 1 位相當於乘 2，右移 1 位相當於除 2
    $m = $m << 1;
    $n = $n >> 1;
    return $n ? russian($m, $n, $res) : $res;
}

echo russian(7, 8); // 輸出 56
?>

代碼解析

• $n & 1 判斷奇數（最低位為 1）。
• $m <<= 1 等價 $m *= 2；$n >>= 1 等價 floor($n / 2)。
• 遞迴終止條件：$n === 0 時返回累加結果 $res。
• 時間複雜度 O(log n)，空間複雜度 O(log n)（遞迴棧）。

迭代版本（避免遞迴棧溢位）

function russian_iter($m, $n) {
    $res = 0;
    while ($n > 0) {
        if ($n & 1) $res += $m;
        $m <<= 1;
        $n >>= 1;
    }
    return $res;
}