python - Karatsuba 乘法实现

Question

我最近实现了 Karatsuba 乘法作为个人练习。我在 pseudocode provided on wikipedia 之后用 Python 编写了我的实现:

procedure karatsuba(num1, num2)if (num1 < 10) or (num2 < 10)    return num1*num2  /* calculates the size of the numbers */  m = max(size_base10(num1), size_base10(num2))  m2 = m/2  /* split the digit sequences about the middle */  high1, low1 = split_at(num1, m2)  high2, low2 = split_at(num2, m2)  /* 3 calls made to numbers approximately half the size */  z0 = karatsuba(low1, low2)  z1 = karatsuba((low1+high1), (low2+high2))  z2 = karatsuba(high1, high2)  return (z2*10^(2*m2)) + ((z1-z2-z0)*10^(m2)) + (z0)

这是我的 python 实现:

def karat(x,y):
    if len(str(x)) == 1 or len(str(y)) == 1:
        return x*y
    else:
        m = max(len(str(x)),len(str(y)))
        m2 = m / 2

        a = x / 10**(m2)
        b = x % 10**(m2)
        c = y / 10**(m2)
        d = y % 10**(m2)

        z0 = karat(b,d)
        z1 = karat((a+b),(c+d))
        z2 = karat(a,c)

        return (z2 * 10**(2*m2)) + ((z1 - z2 - z0) * 10**(m2)) + (z0)

我的问题是关于z0、z1 和z2 的最终合并。
z2 移动了 m 位(其中 m 是两个相乘数中最大的一个的长度)。
该算法不是简单地乘以 10^(m)，而是使用 *10^(2*m2)*，其中 m2 是 m/2 .

我尝试将 2*m2 替换为 m 但得到的结果不正确。我认为这与数字的分配方式有关，但我不太确定发生了什么。

Answer 1

根据您的 Python 版本，您必须或应该将 / 替换为显式的楼层除法运算符 //，这在此处是合适的；它向下舍入以确保您的指数保持整数。

例如，当您将操作数拆分为高位数字(通过除以 10^m2)和低位数字(通过取残差模 10^m2)时，这是必不可少的) 这不适用于小数 m2。

这也解释了为什么 2 * (x//2) 不一定等于 x 而 x-1 如果 x 是奇数.在算法的最后一行，2 m2 是正确的，因为您所做的是将 a 和 c 归零。

如果您使用的是较旧的 Python 版本，您的代码可能仍然有效，因为 / 在应用于整数时曾被解释为底除法。

def karat(x,y):
    if len(str(x)) == 1 or len(str(y)) == 1:
        return x*y
    else:
        m = max(len(str(x)),len(str(y)))
        m2 = m // 2

        a = x // 10**(m2)
        b = x % 10**(m2)
        c = y // 10**(m2)
        d = y % 10**(m2)

        z0 = karat(b,d)
        z1 = karat((a+b),(c+d))
        z2 = karat(a,c)

        return (z2 * 10**(2*m2)) + ((z1 - z2 - z0) * 10**(m2)) + (z0)