大数乘法的算法
大数乘法的关键在于如何用字符串来模拟大数乘法。方法有如下几种：模拟普通的手算乘法、利用代数方法优化的乘法、快速傅立叶变换FFT。
各算法的优点
- 模拟普通手算乘法：算法简单、空间复杂度小。时间复杂度为
O(n^2)。 - 利用代数方法优化的乘法：使用递归求解，空间复杂度较大。算法复杂，需要定义大数加法，大数减法。时间复杂度降低到
O(n^1.5)。 - 快速傅立叶变换FFT：基于FFT的大数乘法时间复杂度
O(nlogn)。快速傅立叶变换据数值分析老师说是本世纪最为伟大的算法。
下边主要对利用代数方法优化的乘法进行介绍。
分析
代数优化
- 假设大数P、Q的长度为m和n，
P = (A * 10^k + B)，Q = (C * 10^k + D)。 k = min(m / 2, n / 2)。PQ = (A * 10^k + B)(C * 10^k + D) = AC * 10 ^2k + (AD + BC) * 10^k + BD。- 以乘法操作作为主要操作，采用master定理可知，时间复杂度为
O(n^2)。此时与普通的手算乘法并没有不同。 - 用于减少时间复杂度的关键，
(A - B)(C - D) = AC - AD - BC + BD - 带入后得，
AC * 10 ^2k + (AC + BD - (A-B)(C-D)) * 10^k + BD。 - 由于我们以乘法操作作为主要操作，因此每一层递归中只需要3次乘法。因此时间复杂度减少为
O(n^1.5)。