Stanford Algorithms 1.3 记录

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