3

我最近将 Karatsuba 乘法作为个人练习。我按照wikipedia 上提供的伪代码用 Python 编写了我的实现：

程序 karatsuba(num1, num2)
如果 (num1 < 10) 或 (num2 < 10)
    返回 num1*num2
  /* 计算数字的大小 */
  m = max(size_base10(num1), size_base10(num2))
  m2 = m/2
  /* 围绕中间分割数字序列 */
  high1, low1 = split_at(num1, m2)
  high2, low2 = split_at(num2, m2)
  /* 对大约一半大小的数字进行 3 次调用 */
  z0 = karatsuba(low1, low2)
  z1 = karatsuba((low1+high1), (low2+high2))
  z2 = karatsuba(high1, high2)
  返回 (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。

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

4

7 回答 7

12

根据您的 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)
于 2017-02-19T06:57:31.270 回答
2

我已经实现了相同的想法，但我将 2 位乘法限制为基本情况，因为我可以减少函数中的浮点乘法

import math

def multiply(x,y):
    sx= str(x)
    sy= str(y)
    nx= len(sx)
    ny= len(sy)
    if ny<=2 or nx<=2:
        r = int(x)*int(y)
        return r
    n = nx
    if nx>ny:
        sy = sy.rjust(nx,"0")
        n=nx
    elif ny>nx:
        sx = sx.rjust(ny,"0")
        n=ny
    m = n%2
    offset = 0
    if m != 0:
        n+=1
        offset = 1
    floor = int(math.floor(n/2)) - offset
    a = sx[0:floor]
    b = sx[floor:n]
    c = sy[0:floor]
    d = sy[floor:n]
    print(a,b,c,d)

    ac = multiply(a,c)
    bd = multiply(b,d)

    ad_bc = multiply((int(a)+int(b)),(int(c)+int(d)))-ac-bd
    r = ((10**n)*ac)+((10**(n/2))*ad_bc)+bd

    return r

print(multiply(4,5))
print(multiply(4,58779))
print(int(multiply(4872139874092183,5977098709879)))
print(int(4872139874092183*5977098709879))
print(int(multiply(4872349085723098457,597340985723098475)))
print(int(4872349085723098457*597340985723098475))
print(int(multiply(4908347590823749,97098709870985)))
print(int(4908347590823749*97098709870985))
于 2018-01-02T14:52:00.630 回答
1

您已将 m2 用作浮点数。它必须是一个整数。

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)
于 2020-07-30T12:36:37.967 回答
1

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

这是您如何为递归调用拆分号码的核心。如果您选择使用奇数n，则将n//2向下舍入到最接近的整数，这意味着您的第二个数字的长度为floor(n/2)并且您必须用floor(n/2)零填充第一个数字。由于我们对两个数字都使用相同n的数字，因此这两个数字都适用。这意味着如果您在最后一步坚持原始奇数n，您将使用原始n零填充第一项，而不是由第一个填充加上第二个填充（floor(n/2)*2）的组合产生的零数

于 2018-01-16T20:05:29.843 回答
0

您的代码和逻辑是正确的，您的基本案例只是存在问题。由于根据算法 a,b,c,d 是 2 位数字，您应该修改基本情况并在基本情况下保持 x 和 y 的长度等于 2。

于 2018-07-28T21:23:47.690 回答
0

我认为最好使用math.log10函数来计算位数而不是转换为字符串，如下所示：

def number_of_digits(number):
  """
  Used log10 to find no. of digits
  """
  if number > 0:
    return int(math.log10(number)) + 1
  elif number == 0:
    return 1
  else:
    return int(math.log10(-number)) + 1 # Don't count the '-'
于 2020-02-01T00:41:46.660 回答
-1

基本情况if len(str(x)) == 1 or len(str(y)) == 1: return x*y不正确。如果您针对大整数运行答案中给出的任一 python 代码，该karat()函数将不会产生正确的答案。

要使代码正确，您需要将基本情况更改为if len(str(x) < 3 or len(str(y)) < 3: return x*y.

下面是 Paul Panzer 正确乘以大整数的答案的修改实现。

def karat(x,y):
    if len(str(x)) < 3 or len(str(y)) < 3:
        return x*y

    n = max(len(str(x)),len(str(y))) // 2

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

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

    return ((10**(2*n))*z2)+((10**n)*(z1-z2-z0))+z0
于 2018-08-19T12:46:48.553 回答