b 进制位置记数法:
数 u = (u_{n-1} u_{n-2} ... u₁ u₀)_b
     = u_{n-1} × b^{n-1} + u_{n-2} × b^{n-2} + ... + u₁ × b + u₀

其中 0 ≤ uᵢ < b

常用进制:
- 二进制 (b=2): 计算机内部表示
- 八进制 (b=8): 早期计算机
- 十六进制 (b=16): 现代计算机
- 十进制 (b=10): 人类习惯

算法 A (高精度加法):
给定 u = (u_{n-1}...u₀)_b 和 v = (v_{n-1}...v₀)_b
求 w = u + v

A1. [初始化] j ← 0, k ← 0
A2. [单字相加] t ← uⱼ + vⱼ + k
     wⱼ ← t mod b
     k ← ⌊t/b⌋
A3. [循环] j ← j + 1
     如果 j < n，返回 A2
A4. [结束] wₙ ← k

时间复杂度: O(n)
空间复杂度: O(n)

算法 M (多精度乘法):
u = (u_{n-1}...u₀)_b
v = (v_{n-1}...v₀)_b

M1. [初始化] k ← 0
M2. [j=0 的乘法] 计算 u × v₀，结果加到 w 的第 0 到 n 位
M3. [循环] j ← j + 1
     如果 j < n，计算 u × vⱼ，结果加到 w 的第 j 到 j+n 位
     返回 M3

时间复杂度: O(n²) 次单字乘法

Karatsuba 算法 (1960):

将 u 和 v 各分为两半:
u = u₁ × B + u₀  (B = b^{n/2})
v = v₁ × B + v₀

u × v = u₁v₁ × B² + (u₁v₀ + u₀v₁) × B + u₀v₀

关键观察:
u₁v₀ + u₀v₁ = (u₁ + u₀)(v₁ + v₀) - u₁v₁ - u₀v₀

所以只需要 3 次 n/2 位乘法:
1. u₁v₁
2. u₀v₀
3. (u₁ + u₀)(v₁ + v₀)

递推式: T(n) = 3T(n/2) + O(n)
解: T(n) = O(n^{log₂ 3}) = O(n^{1.585})

对比:
n = 1000 位:
- 学校乘法: 1,000,000 次操作
- Karatsuba: ~24,000 次操作
- 加速比: ~42x

Toom-Cook 算法 (1963):
- 将数字分为 k 段
- 复杂度: O(n^{1+ε})，ε 随 k 增大而减小
- k=3: O(n^{1.465})
- k=5: O(n^{1.376})

Schönhage-Strassen 算法 (1971):
- 基于 FFT
- 复杂度: O(n log n log log n)
- 适用于超大整数（数万位以上）

Harvey-van der Hoeven 算法 (2019):
- 复杂度: O(n log n)
- 理论上最优，但常数极大
- 实际中尚未实用

IEEE 754 浮点数格式:
(-1)^s × 1.f × 2^{e-bias}

单精度 (32 bit): 1 符号 + 8 指数 + 23 尾数
双精度 (64 bit): 1 符号 + 11 指数 + 52 尾数

浮点加法:
1. 对阶: 将较小指数的数右移，使指数相同
2. 尾数相加
3. 规格化: 调整结果使尾数在 [1, 2) 范围内
4. 舍入: 根据舍入模式处理多余位

精度问题:
0.1 的二进制表示: 0.0001100110011... (无限循环)
0.1 + 0.2 = 0.30000000000000004 (双精度)

解决方案:
- 使用 decimal 类型（金融计算）
- 使用整数运算（以分为单位）
- 使用 epsilon 比较: |a - b| < ε

def karatsuba(x, y):
    if x < 10 or y < 10:
        return x * y
    
    n = max(len(str(x)), len(str(y)))
    half = n // 2
    
    # 分割
    high1, low1 = divmod(x, 10 ** half)
    high2, low2 = divmod(y, 10 ** half)
    
    # 3 次递归乘法
    z0 = karatsuba(low1, low2)
    z2 = karatsuba(high1, high2)
    z1 = karatsuba(low1 + high1, low2 + high2) - z2 - z0
    
    return z2 * 10 ** (2 * half) + z1 * 10 ** half + z0

# 验证
print(karatsuba(123456789, 987654321))
# 输出: 121932631112635269
print(123456789 * 987654321)
# 输出: 121932631112635269