大数乘法的算法
大数乘法的关键在于如何用字符串来模拟大数乘法。方法有如下几种:模拟普通的手算乘法、利用代数方法优化的乘法、快速傅立叶变换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)
。