分治法求大整数乘法通过将n位整数x=a×10ⁿ/²+b、y=c×10ⁿ/²+d拆分，用p₁=ac、p₂=bd、p₃=(a+b)(c+d)仅3次递归乘法计算xy=p₁×10ⁿ+(p₃−p₁−p₂)×10ⁿ/²+p₂，时间复杂度降至o(n^log₂3)≈o(n¹·⁵⁸⁵)。

分治法求大整数乘法，核心是把两个 n 位大整数 拆成两半，递归计算更小的子问题，再合并结果，避开传统 O(n²) 的逐位相乘，将时间复杂度降到约 O(n^log₂3) ≈ O(n^1.585)。关键不是“分”，而是“怎么合得巧”——用 3 次递归乘法替代朴素的 4 次。

拆分方式与数学原理

设两个 n 位整数 X 和 Y（n 为偶数，不足补 0），令：

• X = A × 10^n/2 + B，其中 A、B 分别是 X 的高 n/2 位和低 n/2 位
• Y = C × 10^n/2 + D，同理 C、D 是 Y 的高、低位
• 则 XY = AC × 10ⁿ + (AD + BC) × 10^n/2 + BD

朴素算法需算 AC、AD、BC、BD 共 4 次乘法；Karatsuba 算法改用：

• P₁ = AC
• P₂ = BD
• P₃ = (A + B)(C + D)
• 则 AD + BC = P₃ − P₁ − P₂

这样只用 3 次递归乘法，代价是增加加减和位移（即乘 10^k），但总体复杂度显著下降。

Java Maven Secondary Analysis

分析ZIP压缩包或GitLab仓库中的Java Maven项目，确定二次开发范围、类数量、模块分布及生产相关指标。

下载

递归终止条件与位数处理

递归不能无限拆分，需设合理出口：

• 当数字位数 ≤ 3（或 ≤ 64 位，视语言整型上限而定），直接转为 long 或 BigInteger 的内置乘法
• 若位数为奇数，可统一向上取偶（如 5 位 → 按 6 位拆），高位补 0 不影响值
• 字符串表示时，拆分前先去除前导零，避免空串或全零导致递归异常

Java 实现要点（以字符串输入为例）

Java 中大整数常用 String 或 BigInteger 表示。若手写分治，推荐用 String 避免 BigInteger 内部优化干扰学习目的：

• 用 substring 拆分高低位，注意索引边界（如长度 len，则 high = str.substring(0, len/2)，low = str.substring(len/2)）
• 加法、减法需自己实现字符串版（注意进位/借位、符号、长度对齐），这是基础支撑
• 位移（×10^k）等价于字符串末尾补 k 个 '0'；合并时按权重拼接：P₁ + '0...0'（n 个 0）+ (P₃−P₁−P₂) + '0...0'（n/2 个 0）+ P₂
• 递归调用前，确保 A+B、C+D 的位数不超限（它们最多比原数多 1 位，仍可递归）

实际效果与注意事项

Karatsuba 在 n 较大时才明显快于朴素法（一般 n > 1000 位才有优势）：

• 小规模用简单乘法更快（递归开销和字符串操作成本高）
• Java 中若直接用 BigInteger，其 multiply() 方法已内置 Karatsuba（n 较大时）和 Toom-Cook（更大时），无需重复造轮子；但理解原理对分析算法行为很重要
• 注意栈深度：n=10⁵ 时递归约 log₂(10⁵) ≈ 17 层，安全；但若未设好终止条件易 StackOverflowError

Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南