泛型编程之乘法

埃及乘法

• 目标
• 奇数odd
• 被乘数和乘数
• 尾递归函数
• • r + n a r+na r+na
• 扩展加法链
• 代码

目标

学习泛型编程。了解最古老的算法。从运行结果来看，没有明显变化。乘法已是基本运算，电光火石间就完成了。

泛型乘法验证

奇数odd

公元前两千年的埃及人，已经知道奇数和偶数。它是乘法的关键。在埃及乘法发明之前应该都是累加的。乘以2，加倍的乘法是最好算的。我们把乘数加倍，把被乘数减半，反复这样做，这就是“埃及乘法”，或者叫“俄罗斯农夫算法”。

被乘数和乘数

从叠加变成乘法来看，被乘除就是叠加次数，被叠加的次数。乘数就是被叠加的那个数。之前他们的顺序总容易弄反，或者搞不清。今天是看到出处，原型了。

尾递归函数

文章递归的改造——间隔挑硬币里讲过一些改造递归调用函数的方法。现在讲的乘法是一个更好的例子。尾递归函数是使用与形式参数完全对应的实际参数来进行递归调用，而且只在返回值里进行递归调用。尾递归函数就可以改成迭代的形式。

r + n a r+na r+na

r 是在运算过程中会持续更新的值，用来累计计算好的那部分 n a na na乘积。通过引入变量，得到了尾递归的乘法算法。

def weidigui(r,n,a):
    if odd(n):
        r += a
        if n==1:return r
    n = half(n)
    a += a
    return weidigui(r,n,a)

half(n)是把被乘数减半的方法。

扩展加法链

埃及算法不是总是最好的。当被乘数是15时，可以只加五次就行了。埃及算法的时间复杂度是 log ⁡ 2 15 = 3.9068905956085187 \log_{2}{15}=3.9068905956085187 log2​15=3.9068905956085187，但是要执行的加法次数是六。

def beichengshu15(a):
    b = (a+a)+a
    c = b+b
    return (c+c)+b

什么东西都可以做得再极致。

代码

def odd(n):
    return n&0x1
def half(n):
    return n>>1
def mult_acc(r,n,a):
    while True:
        if odd(n):
            r += a
            if 1==n:return r
        n = half(n)
        a += a
        
def multiply(n,a):
    while not odd(n):
        a += a
        n = half(n)
    if 1==n:return a
    #even(n-1)-->n-1 != 1
    return mult_acc(a,half(n-1),a+1)