浅鱼

考察两个数的乘法的不同实现方案
这是上算法课的一道算法思考题。原题如下:考察两个数乘法的不同实现方案(分析时间性能)。我对这个问题的理解是:两个大...
扫描右侧二维码阅读全文
06
2018/03

考察两个数的乘法的不同实现方案

这是上算法课的一道算法思考题。原题如下:

考察两个数乘法的不同实现方案(分析时间性能)。

我对这个问题的理解是:两个大数的乘法,有哪些实现的算法方案?

下面是我收集并整理的一些实现算法:

1.普通大数乘法:分为普通大数乘法移位进位法,时间复杂度为O(n²);
2.分治算法:最简单的是Karatsuba乘法,一般化以后有Toom-Cook乘法,时间复杂度为请输入图片描述
3.快速傅里叶变换FFT:(为了避免精度问题,可以改用快速数论变换FNTT),时间复杂度O(nlgn)。具体可参照Schönhage–Strassen algorithm
4.Furer’s algorithm:在渐进意义上FNTT还快的算法。不过好像不太实用,这里就不作介绍了。大家可以参考维基百科Fürer’s algorithm
5.使用 GMP(GNU多重精度运算库),这个算法大家可以参考维基百科GNU多重精度运算库

下面我主要讲一下前面3种方法,后面三种我自己目前也不是很懂。我理解的比较深刻的就只有普通大数乘法分治算法

1. 普通大数乘法。
普通大数乘法主要有逐位相乘处理进位法移位进位法。他们的优点是空间复杂度低,实现简单,但时间复杂度为O(n²)

(1)逐位相乘处理进位法。

乘积是逐位相乘,也就是aibj,结果加入到积C的第i+j位,最后处理进位即可。思路为:

  1. 转换并反转,字符串转换为数字并将字序反转;
  2. 逐位相乘,结果存放在result_num[i+j]中;
  3. 处理进位,消除多余的0;
  4. 转换并反转,将计算结果转换为字符串并反转。

例如:
A =17 = 1*10 + 7 = (7,1)最后是十进制的幂表示法,幂次是从低位到高位,以下同。
B=25 = 2*10 + 5 = (5, 2);
C = A B = (7 5, 1 5 + 2 7, 1 * 2) = (35, 19, 2) = (5, 22, 2) = (5, 2, 4)=425。
该算法时间复杂度为为O(n2)。

上面的思路还是很清晰的,但代码有些过长,考虑优化如下:

a. 上述思路是先转换反转,其实无需先将全部字符串转换为数字的,可即用即转,节约空间;
b. 无需等到逐位相乘都结束,才处理进位,可即乘即进;
c. 无需等到所有结果出来后,将结果转换为字符,可即乘即转。

优化后时间复杂度不变,但节省了空间,代码更简洁。

(2)移位进位法。

移位进位法也是普通的大数相乘算法,其时间复杂度也为O(n²)。

例如:按照乘法的计算过程来模拟计算:

     1 2

    × 3 6

   --------------
     7 2
在这个计算过程中,2×6=12。本位保留2,进位为1。

2.分治算法。
分治算法的时间性能要好很多,时间复杂度降低为请输入图片描述,但其实现需要配合字符串模拟加减法操作,实现较为复杂。如图:

请输入图片描述

虽然上面的原理是对应2进制的,但是对于10进制也同样可行。

请输入图片描述

3.FFT(快速傅里叶变换)。
FFT(FastFourierTransformation) 即快速傅里叶变换,是DFT的加速算法,利用单位复数根的特殊性质,可以在O(nlogn)的时间内算出DFT(DiscreteFourierTransformation)即离散傅里叶变换及DFT逆运算。

整个算法需要较强的数学功底,思想较为复杂。下面这篇文章详细说明了FFT的计算过程:

使用快速傅里叶变换计算大整数乘法

参考文献:
1、大数乘法;
2、 程序员编程艺术第三十~三十一章:字符串转换成整数,通配符字符串匹配
3、大数乘法的几种算法分析及比较(2014腾讯南京笔试题)
4、FFT算法学习笔记
5、分治法实现大数相乘C#实现
6、使用快速傅里叶变换计算大整数乘法
7、FFT(快速傅里叶变换)算法学习笔记
8、大数乘法问题及其高效算法

Last modification:March 6th, 2018 at 01:27 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment