大数乘法(Multiply Strings)

大数乘法的算法

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

Update your browser to view this website correctly. Update my browser now

×