Python实现Karatsuba大整数乘法算法详解

Karatsuba算法原理与优势

传统长乘法采用按位相乘的方式，其时间复杂度为 O(n ^ 2)。本文将介绍一种更高效的算法——Karatsuba算法，该算法的时间复杂度为 O (n ^ log 3)，其中 log 表示以 2 为底的对数。

原理介绍

Karatsuba算法要求参与运算的乘数与被乘数满足两个条件：首先，两者的位数必须相同；其次，位数必须是 2 的幂次，例如 2 ^ 2、2 ^ 3、2 ^ 4 或 2 ^ n 等形式。

为了直观理解Karatsuba算法的使用方式，我们先通过几个简单示例进行分析。

两位数与四位数计算示例

两位数相乘示例

假设被乘数 A = 85，乘数 B = 41。具体操作步骤如下：

将 A 和 B 分别一分为二，定义 p = A 的前半部分 = 8，q = A 的后半部分 = 5，r = B 的前半部分 = 4，s = B 的后半部分 = 1，且 n = 2。通过基础数学运算推导：

A * B = pq * rs = (p * 10 + q) * (r * 10 + s) = p * r * 10 ^ 2 + (p * s + q * r ) * 10 + q * s。

定义 u = p * r，v =（p - q) * (s - r)，w = q * s。因此，A * B 可表示为 u * 10 ^ 2 + (u + v + w) * 10 + w。

代入数值进行求解的过程如下：

A * B = 85 * 41 = (8 * 10 + 5) * ( 4 * 10 + 1) = 8 * 4 * 10 * 10 + (8 * 1 + 5 * 4) * 10 + 5 * 1。

其中 u = 8 * 4 = 32，v = (8 - 5) * (1 - 4) = -9，w = 5 * 1 = 5。

最终计算结果为 A * B = 32 * 100 + (32 - 9 + 5) * 10 + 5 = 3485。该结果与传统长乘法一致。

四位数相乘示例

假设被乘数 A = 8537，乘数 B = 4123。具体操作步骤如下：

将 A 和 B 分别一分为二，定义 p = A 的前半部分 = 85，q = A 的后半部分 = 37，r = B 的前半部分 = 41，s = B 的后半部分 = 23，且 n = 4。

其中，u = 85 * 41，v = (85 - 37) * (23 - 41)，w = 37 * 23。

A * B = 8537 * 4123 = u * 10 ^ 4 + (u + v + w) * 10 ^ 2 + w = 3485_0000 + 34_7200 + 851 = 35198051。

在计算 u、v、w 的过程中涉及两位数乘法，此处继续使用Karatsuba算法得出结果。

N位数递归计算逻辑

N位数相乘通用逻辑

设 n 为乘数与被乘数的位数，定义 p = A 的前半部分，q = A 的后半部分，r = B 的前半部分，s = B 的后半部分。

其中，u = p * r，v = (p - q) * (s - r)，w = q * s。

因此 A * B = u * 10 ^ n + (u + v + w) * 10 ^ (n / 2) + w。

u、v、w 的计算本质上是两个 n / 2 位的乘法运算。通过递归调用Karatsuba算法计算 u、v、w 的数值。在计算 n / 2 位乘法时，会进一步分解为 n / 4 位的乘法……以此类推，直到处理两个个位数乘法，直接返回结果。层层返回后，最终得到 N 位数的乘法结果。

时间复杂度推导

时间复杂度分析

传统长乘法的时间复杂度为 O (n ^ 2)。例如两个 N 位数相乘，需按位相乘，共计算 N * N 次乘法。而Karatsuba算法每层需进行三次乘法和两次加法（以及若干次加法），每次使用算法后，乘法规模减半。

对于两个 n = 2 ^ K 位数的乘法运算，需计算 3 ^ k 次乘法。由于 K = log n（底数为 2），则 3 ^ K = 3 ^ log n = 2 ^ (log 3 * log n) = 2 ^ (log n * log 3) = n ^ log 3（底数为 2）。

Python代码实现与测试

代码实现

from math import log2, ceil
 
def pad(string: str, real_len: int, max_len: int) -> str:
  pad_len: int = max_len - real_len
  return f"{'0' * pad_len}{string}"
 
 
def kara(n1: int, n2: int) -> int:
  if n1 < 10 or n2 < 10:
    return n1 * n2
  n1_str: str = str(n1)
  n2_str: str = str(n2)
  n1_len: int = len(n1_str)
  n2_len: int = len(n2_str)
  real_len: int = max(n1_len, n2_len)
  max_len: int = 2 ** ceil(log2(real_len))
  mid_len: int = max_len >> 1
  n1_pad: str = pad(n1_str, n1_len, max_len)
  n2_pad: str = pad(n2_str, n2_len, max_len)
  p: int = int(n1_pad[:mid_len])
  q: int = int(n1_pad[mid_len:])
  r: int = int(n2_pad[:mid_len])
  s: int = int(n2_pad[mid_len:])
  u: int = kara(p, r)
  v: int = kara(q-p, r-s)
  w: int = kara(q, s)
  return u * 10 ** max_len + (u+v+w) * 10 ** mid_len + w

输出结果：

==> kara(123456, 9734) == 123456 * 9734

==> kara(1234233456756, 32459734) == 1234233456756 * 32459734

以上为本文全部内容，希望能为您的学习提供帮助，欢迎支持本站。