文章目录

• • @[toc]
  • • 问题描述
    • 基础算法
    • • 时间复杂性
    • 优化算法
    • • 时间复杂性
    • `Python`实现

个人主页：丷从心.

系列专栏：Python基础

学习指南：Python学习指南

---

问题描述

• 设$X$和$Y$都是$n$位二进制整数，计算它们的乘积$XY$

---

基础算法

• 将$n$位二进制整数$X$和$Y$都分为$2$段，每段的长为$n/2$位（假设$n$是$2$的幂）
  • $X=A\times 2^{n/2}+B$
  • $Y=C\times 2^{n/2}+D$
  • $XY=(A\times 2^{n/2}+B)(C\times 2^{n/2}+D)=AC\times 2^n+(AD+BC)\times 2^{n/2}+BD$

时间复杂性

• 如果按此式计算$XY$，必须进行$4$次$n/2$位整数的乘法，$3$次不超过$2n$位的整数加法，以及$2$次移位，所有这些加法和移位共用$O(n)$步运算

$$T(n)=\{\begin{array}{ll}O(1)& n=1\\ 4T(n/2)+O(n)& n>1\end{array}$$

$$T(n)=O(n^2)$$

---

优化算法

• 要想改进算法的计算复杂性，必须减少乘法次数，把$XY$写成另一种形式
  • $XY=AC\times 2^n+((A-B)(D-C)+AC+BD)\times 2^{n/2}+BD$

时间复杂性

• 需做$3$次$n/2$位整数的乘法，$6$次加减法和$2$次移位

$$T(n)=\{\begin{array}{ll}O(1)& n=1\\ 3T(n/2)+O(n)& n>1\end{array}$$

$$T(n)=O(n^{\log 3})=O(n^{1.59})$$

---

Python实现

def karatsuba_multiply(x, y):# 如果乘数之一为 0, 则直接返回 0if x == 0 or y == 0:return 0# 将乘数转换为字符串, 并获取它们的位数x_str = str(x)y_str = str(y)n = max(len(x_str), len(y_str))# 达到基本情况时, 使用传统的乘法if n == 1:return x * y# 将乘数补齐到相同的位数x_str = x_str.zfill(n)y_str = y_str.zfill(n)# 将乘数划分为两部分m = n // 2high1, low1 = int(x_str[:m]), int(x_str[m:])high2, low2 = int(y_str[:m]), int(y_str[m:])# 递归地计算三个乘法z0 = karatsuba_multiply(low1, low2)z1 = karatsuba_multiply((low1 + high1), (low2 + high2))z2 = karatsuba_multiply(high1, high2)# 计算结果res = (z2 * 10 ** (2 * m)) + ((z1 - z2 - z0) * 10 ** m) + z0return resx = 123456789012345678901234567890
y = 987654321098765432109876543210res = karatsuba_multiply(x, y)print(f'{x} * {y} = {res}')

123456789012345678901234567890 * 987654321098765432109876543210 = 1118682545728135594602764865374020721634181747367148900

---