两个长数字串的全乘快速算法 |
| |
作者姓名: | 李红 |
| |
作者单位: | 广东江海中学 |
| |
摘 要: | 用传统的乘法,对两个长数字串相乘,尤其是借助于计算机执行运算,决不是快速的算法.两个长度为N的数字串相乘,被乘数将依次与乘数的每一个数字位作捷乘,共需N~2个操作.然而,在本文所介绍的方法中,读者将看到,对于长度为N的数字串的所有算术运算,实际上其操作数将≤N×Log N×Log Log N个数进行.本文所介绍的方法是:将乘法看作为乘数与被乘数的卷积运算,然后进行快速付里叶变换(FFT),使卷积运算变为点乘运算,最后再实施逆FFT变换,得到相乘的结果.例如比较以下两个数:234×567的两种相乘方法.
|
本文献已被 CNKI 等数据库收录! |
|