python - 唐津乘法实现

我最近把空手道乘法作为个人练习。我用Python编写的实现遵循pseudocode provided on wikipedia：

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)

Here is my python implementation:

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，结果不正确。我认为这与数字的分割方式有关，但我不确定到底是怎么回事。

最佳答案

根据Python版本的不同，您必须或应该用显式的floor division运算符替换/，这在这里是合适的；它向下取整以确保指数保持整数。
这一点很重要，例如，当将操作数分成高位数（通过floor除以//）和低位数（通过取剩余模10^m2）时，这对于分数10^m2不起作用。
这也解释了为什么如果x是奇数，那么m2不一定等于2 * (x // 2)，而是x。
在算法的最后一行中x-1是正确的，因为您所做的是将2 m2和a的零点返回。
如果您使用的是较旧的Python版本，那么您的代码可能仍然可以工作，因为c在应用于整数时曾被解释为floor division。

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)

关于python - 唐津乘法实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42324419/