Stanford Algorithms是油管上的算法教学视频, 分为I II两部分, 由于本人基础过于薄弱故只能从零开始学习
stay hungry ，stay foolish
谨记. 我的理解是把自己当傻子, 不管你是在看代数概率论还是看计科这种入门课, 从零开始, 从基本结论开始一点点往后, 自然会发现其中的框架. 现在都太浮躁了, 静不下心看书, 很难. 有些人又这么强搞科研那么快发论文, 心里也有些难过和着急. 不过还是好好做自己比较实际.
1.3 Karatsuba Multiplication
一般用于大数的相乘计算(提高效率), 本来的数学原理是这样的(举例说明, 两个位数相等的自然数, 用x, y表示):
那么,
注意到我们会用递归的方式去处理因为我们的数字可能很大, 会不断调用小的数字的乘法; 所以这里的中间项(ad+bc)我们考虑用别的方式来避免它做两次递归. 我们采用的办法是(a+b)(c+d)-ac-bd. 一开始我也好奇这里步骤不是比计算中间项更多吗? 问题在于我们用的是递归, 如果直接算需要两次递归、而用现在这个只要一次.
以下python code来自Wikipedia, 截取了较长的那个数字的一般作为截断位置.
def karatsuba(num1, num2):
# 递归的退出条件
if (num1 < 10) or (num2 < 10):
return num1*num2
num1Str = str(num1)
num2Str = str(num2)
maxLength = max(len(num1Str), len(num2Str))
splitPosition = maxLength / 2
high1, low1 = int(num1Str[:-splitPosition]), int(num1Str[-splitPosition:])
high2, low2 = int(num2Str[:-splitPosition]), int(num2Str[-splitPosition:])
z0 = karatsuba(low1, low2)
z1 = karatsuba((low1 + high1), (low2 + high2))
z2 = karatsuba(high1, high2)
return (z2*10**(2*splitPosition)) + ((z1-z2-z0)*10**(splitPosition)) + z0
