Karatsuba 演算法

Karatsuba 演算法 用於系統對兩個 n 位數字進行快速乘法運算，即系統編譯器計算乘積所需的時間少於普通乘法所需的時間。

通常的乘法方法需要 n² 次計算才能得到最終乘積，因為必須對兩個數字中的所有數字組合進行乘法運算，然後將子乘積相加得到最終乘積。這種乘法方法稱為樸素乘法。

為了更好地理解這種乘法，讓我們考慮兩個 4 位整數：1456 和 6533，並使用樸素方法求出乘積。

所以，1456 × 6533 =？

在這種樸素乘法方法中，由於兩個數字的位數都是 4，因此會執行 16 次一位數 × 一位數的乘法。因此，這種方法的時間複雜度為 O(4²)，因為它需要 4² 步才能計算出最終乘積。

但是，當 n 的值不斷增加時，問題的複雜度也會不斷增加。因此，採用 Karatsuba 演算法進行更快的乘法運算。

Karatsuba 演算法

Karatsuba 演算法的主要思想是將多個子問題的乘法簡化為三個子問題的乘法。加法和減法等算術運算用於其他計算。

對於此演算法，將兩個 n 位數字作為輸入，並將兩個數字的乘積作為輸出。

步驟 1 - 在此演算法中，我們假設 n 是 2 的冪。

步驟 2 - 如果 n = 1，則我們使用乘法表查詢 P = XY。

步驟 3 - 如果 n > 1，則將 n 位數字分成兩半，並使用以下公式表示數字：

X = 10n/2X1 + X2
Y = 10n/2Y1 + Y2

其中，X₁、X₂、Y₁、Y₂ 各有 n/2 位數字。

步驟 4 - 取一個變數 Z = W – (U + V)，

其中，

U = X1Y1, V = X2Y2
W = (X1 + X2) (Y1 + Y2), Z = X1Y2 + X2Y1.

步驟 5 - 然後，在公式中代入值後得到乘積 P：

P = 10n(U) + 10n/2(Z) + V
P = 10n (X1Y1) + 10n/2 (X1Y2 + X2Y1) + X2Y2.

步驟 6 - 透過分別傳遞子問題 (X₁, Y₁)、(X₂, Y₂) 和 (X₁ + X₂, Y₁ + Y₂) 來遞迴呼叫演算法。將返回值分別儲存在變數 U、V 和 W 中。

示例

讓我們使用 Karatsuba 方法解決上面給出的相同問題，1456 × 6533：

Karatsuba 方法採用分治法，將問題分解成多個子問題，並應用遞迴使乘法更簡單。

步驟 1

假設 n 是 2 的冪，將 n 位數字改寫為：

X = 10n/2X1 + X2 Y = 10n/2Y1 + Y2

這給了我們：

1456 = 102(14) + 56 
6533 = 102(65) + 33

首先讓我們嘗試簡化數學表示式，我們得到：

(1400 × 6500) + (56 × 33) + (1400 × 33) + (6500 × 56) = 
104 (14 × 65) + 102 [(14 × 33) + (56 × 65)] + (33 × 56)

上述表示式是給定乘法問題的簡化版本，因為乘以兩個兩位數比乘以兩個四位數更容易解決。

然而，這對於人的思維來說是正確的。但對於系統編譯器而言，上述表示式的複雜度與普通的樸素乘法相同。由於它有 4 個兩位數 × 兩位數的乘法，因此所需的時間複雜度為：

14 × 65 → O(4)
14 × 33 → O(4)
65 × 56 → O(4)
56 × 33 → O(4)
= O (16)

因此，需要進一步簡化計算。

步驟 2

X = 1456 
Y = 6533

由於 n 不等於 1，演算法跳到步驟 3。

X = 10n/2X1 + X2 
Y = 10n/2Y1 + Y2

這給了我們：

1456 = 102(14) + 56 
6533 = 102(65) + 33

計算 Z = W – (U + V)：

Z = (X1 + X2) (Y1 + Y2) – (X1Y1 + X2Y2) 
Z = X1Y2 + X2Y1 
Z = (14 × 33) + (65 × 56)

最終乘積：

P = 10n. U + 10n/2. Z + V 
   = 10n (X1Y1) + 10n/2 (X1Y2 + X2Y1) + X2Y2 
   = 104 (14 × 65) + 102 [(14 × 33) + (65 × 56)] + (56 × 33)

子問題可以進一步分解成更小的子問題；因此，該演算法再次遞迴呼叫。

步驟 3

X₁ 和 Y₁ 作為引數 X 和 Y 傳遞。

所以現在，X = 14，Y = 65

X = 10n/2X1 + X2 
Y = 10n/2Y1 + Y2 
14 = 10(1) + 4 
65 = 10(6) + 5

計算 Z = W – (U + V)：

Z = (X1 + X2) (Y1 + Y2) – (X1Y1 + X2Y2) 
Z = X1Y2 + X2Y1 
Z = (1 × 5) + (6 × 4) = 29 

P = 10n (X1Y1) + 10n/2 (X1Y2 + X2Y1) + X2Y2 
   = 102 (1 × 6) + 101 (29) + (4 × 5) 
   = 910

步驟 4

X₂ 和 Y₂ 作為引數 X 和 Y 傳遞。

所以現在，X = 56，Y = 33

X = 10n/2X1 + X2 
Y = 10n/2Y1 + Y2 
56 = 10(5) + 6 
33 = 10(3) + 3

計算 Z = W – (U + V)：

Z = (X1 + X2) (Y1 + Y2) – (X1Y1 + X2Y2) 
Z = X1Y2 + X2Y1 
Z = (5 × 3) + (6 × 3) = 33 

P = 10n (X1Y1) + 10n/2 (X1Y2 + X2Y1) + X2Y2 
= 102 (5 × 3) + 101 (33) + (6 × 3) 
= 1848

步驟 5

X₁ + X₂ 和 Y₁ + Y₂ 作為引數 X 和 Y 傳遞。

所以現在，X = 70，Y = 98

X = 10n/2X1 + X2 
Y = 10n/2Y1 + Y2 
70 = 10(7) + 0 
98 = 10(9) + 8

計算 Z = W – (U + V)：

Z = (X1 + X2) (Y1 + Y2) – (X1Y1 + X2Y2) 
Z = X1Y2 + X2Y1 
Z = (7 × 8) + (0 × 9) = 56 

P = 10n (X1Y1) + 10n/2 (X1Y2 + X2Y1) + X2Y2 
= 102 (7 × 9) + 101 (56) + (0 × 8) 
=

步驟 6

最終乘積：

P = 10n. U + 10n/2. Z + V

U = 910 
V = 1848 
Z = W – (U + V) = 6860 – (1848 + 910) = 4102

將值代入方程：

P = 10n. U + 10n/2. Z + V 
P = 104 (910) + 102 (4102) + 1848 
P = 91,00,000 + 4,10,200 + 1848 
P = 95,12,048

分析

Karatsuba 演算法是一個遞迴演算法；因為它在執行期間呼叫自身較小的例項。

根據該演算法，它只在 n/2 位數字上呼叫自身三次，以獲得兩個 n 位數字的最終乘積。

現在，如果 T(n) 表示執行乘法時所需的數字乘法次數，

T(n) = 3T(n/2)

此方程是一個簡單的遞推關係，可以解為：

Apply T(n/2) = 3T(n/4) in the above equation, we get:
T(n) = 9T(n/4)
T(n) = 27T(n/8)
T(n) = 81T(n/16)
.
.
.
.
T(n) = 3i T(n/2i) is the general form of the recurrence relation 
of Karatsuba algorithm.

可以使用主定理求解遞推關係，因為我們有一個形式為的劃分函式：

T(n) = aT(n/b) + f(n), where, a = 3, b = 2 and f(n) = 0 
which leads to k = 0.

由於 f(n) 表示遞迴外部完成的工作，即 Karatsuba 中的加法和減法算術運算，這些算術運算不會影響時間複雜度。

檢查 'a' 和 'b^k' 之間的關係。

a > bk = 3 > 20

根據主定理，應用情況 1。

T(n) = O(nlogb a)
T(n) = O(nlog 3)

Karatsuba 演算法快速乘法的時間複雜度為O(n^{log 3})。

示例

在 Karatsuba 演算法的完整實現中，我們試圖乘以兩個較大的數字。這裡，由於long 資料型別最多接受 18 位小數，我們將輸入作為long 值。Karatsuba 函式被遞迴呼叫，直到獲得最終乘積。

#include <stdio.h>
#include <math.h>
int get_size(long);
long karatsuba(long X, long Y){
   
   // Base Case
   if (X < 10 && Y < 10)
      return X * Y;
   
   // determine the size of X and Y
   int size = fmax(get_size(X), get_size(Y));
   if(size < 10)
      return X * Y;
   
   // rounding up the max length
   size = (size/2) + (size%2);
   long multiplier = pow(10, size);
   long b = X/multiplier;
   long a = X - (b * multiplier);
   long d = Y / multiplier;
   long c = Y - (d * size);
   long u = karatsuba(a, c);
   long z = karatsuba(a + b, c + d);
   long v = karatsuba(b, d);
   return u + ((z - u - v) * multiplier) + (v * (long)(pow(10, 2 * size)));
}
int get_size(long value){
   int count = 0;
   while (value > 0) {
      count++;
      value /= 10;
   }
   return count;
}
int main(){

   // two numbers
   long x = 145623;
   long y = 653324;
   printf("The final product is: %ld\n", karatsuba(x, y));
   return 0;
}

The final product is: 95139000852

#include <iostream>
#include <cmath>
using namespace std;
int get_size(long);
long karatsuba(long X, long Y){

   // Base Case
   if (X < 10 && Y < 10)
      return X * Y;

   // determine the size of X and Y
   int size = fmax(get_size(X), get_size(Y));
   if(size < 10)
      return X * Y;

   // rounding up the max length
   size = (size/2) + (size%2);
   long multiplier = pow(10, size);
   long b = X/multiplier;
   long a = X - (b * multiplier);
   long d = Y / multiplier;
   long c = Y - (d * size);
   long u = karatsuba(a, c);
   long z = karatsuba(a + b, c + d);
   long v = karatsuba(b, d);
   return u + ((z - u - v) * multiplier) + (v * (long)(pow(10, 2 * size)));
}
int get_size(long value){
   int count = 0;
   while (value > 0) {
      count++;
      value /= 10;
   }
   return count;
}
int main(){

   // two numbers
   long x = 145623;
   long y = 653324;
   cout << "The final product is: " << karatsuba(x, y) << endl;
   return 0;
}

The final product is: 95139000852

import java.io.*;
public class Main {
   static long karatsuba(long X, long Y) {
      // Base Case
      if (X < 10 && Y < 10)
         return X * Y;
      // determine the size of X and Y
      int size = Math.max(get_size(X), get_size(Y));
      if(size < 10)
         return X * Y;
      // rounding up the max length
      size = (size/2) + (size%2);
      long multiplier = (long)Math.pow(10, size);
      long b = X/multiplier;
      long a = X - (b * multiplier);
      long d = Y / multiplier;
      long c = Y - (d * size);
      long u = karatsuba(a, c);
      long z = karatsuba(a + b, c + d);
      long v = karatsuba(b, d);
      return u + ((z - u - v) * multiplier) + (v * (long)(Math.pow(10, 2 * size)));
   }
   static int get_size(long value) {
      int count = 0;
      while (value > 0) {
         count++;
         value /= 10;
      }
      return count;
   }
   public static void main(String args[]) {
      // two numbers
      long x = 145623;
      long y = 653324;
      System.out.print("The final product is: ");
      long product = karatsuba(x, y);
      System.out.println(product);
   }
}

The final product is: 95139000852

import math
def karatsuba(X, Y):
    if X < 10 and Y < 10:
        return X * Y
    size = max(get_size(X), get_size(Y))
    if size < 10:
        return X * Y
    size = (size // 2) + (size % 2)
    multiplier = 10 ** size
    b = X // multiplier
    a = X - (b * multiplier)
    d = Y // multiplier
    c = Y - (d * size)
    u = karatsuba(a, c)
    z = karatsuba(a + b, c + d)
    v = karatsuba(b, d)
    return u + ((z - u - v) * multiplier) + (v * (10 ** (2 * size)))
def get_size(value):
    count = 0
    while value > 0:
        count += 1
        value //= 10
    return count
x = 145623
y = 653324
print("The final product is: ", end="")
product = karatsuba(x, y)
print(product)

The final product is: 95139000852