Big Number Multiplication 大数乘法

  • Python实现
  • 手工计算(竖式计算)
  • Divide and Conquer 分治法(Karatsuba Multiplication)

Stanford算法公开课第一周作业是两个64位数相乘。起初我用Python采用手工计算方法写,但没有考虑数字过大的情况,得到的结果是127位的,电脑限制了128位的结果。后续在网上看了其他人的解决方法,利用了字符串储存结果,避免了位数限制。

在牛客网里我也找到了这一道题,测试用例很多,可以测试代码结果:大数相乘试题

在这篇里,我会列出大数乘法的几种主流方法,并附上部分实现代码。

Python实现

Python语言支持自动高精度,集成度较高。严格来讲这不是算法,但可以快速解决问题。

m,n = map(int, input().split())  
print(m * n)

手工计算(竖式计算)

特点:时间复杂度为O(n^2),空间复杂度低,简单明了。

方法:大数A和B逐位相乘,即为a_i b_j ,结果加入到乘积C的第i+j位,即为 c_{ij} ,同时处理进位问题。和日常计算不同,我采用倒序处理方法,这样循环得到的高位就不会被后续计算影响。

示例:

代码:https://github.com/xueqiwang0v0/BigNumberMultiplication

Divide and Conquer 分治法(Karatsuba Multiplication)

分治法是一种解决问题的方法,不是特定用于解决大数乘法的算法。Karatsuba方法是利用了分治法来解决大数乘法问题,本质上解决一个递归问题。相比竖式计算,时间复杂度降低。但实际操作的时候较为麻烦。

方法:假设乘数x,y都为n位数

  1. 将乘数x,y写成x=10^\frac{n}{2}a+by=10^\frac{n}{2}c+d
  2. 计算ac
  3. 计算bd
  4. ad+bc=(a+b)(c+d)-ac-bd
  5. 得到xy=10^n ac+10^\frac{n}{2}(ad+bc)+bd

参考资料

You May Also Like

About the Author: 雪球

一个在读的工科研究生 一个努力追赶时代脚步的人 Github: https://github.com/xueqiwang0v0 LinkedIn: https://www.linkedin.com/in/xueqi-wang-0939b51a6/

1 Comment

发表评论

邮箱地址不会被公开。 必填项已用*标注