Large integer multiplication: a key topic in Divide-and-Conquer Algorithm Design

大整数相乘

问题背景

考虑两个均为n位的整数X和Y，在求取它们的乘积XY的过程中，默认采用传统的基础算法技巧。然而这种传统的方法虽然简单直接但存在明显的局限性，在处理较大的数值时效率显著下降。（尤其是当n值较大时）

若每次运算仅涉及两位数字相乘或相加，则上述传统方法所需的时间复杂度为O(n^2)阶。基于此不足之处，在后续章节中我们将会介绍一种更为高效的大整数相乘算法。

分治法

基本思想：
分析中的divide-and-conquer technique将一个规模较大的large-scale problems分解为several相互独立的同类型subproblems, 然后recursively address这些subproblems以获得各自的结果, 最终通过整合这些subproblems' solutions to construct the solution for the original problem.

• 适用条件：

1. 该问题是经过分析后发现其大小在一定范围内就可实现相对容易地解决。
2. 该问题是可以通过划分的方式被划分为多个规模较小且相同的子
3. 通过将这些子
4. 各个子问题是相互独立且互不重叠以确保不会出现重复计算的情况