0

所以我目前在 python 中实现 Karatsuba 的算法，我遇到了一个非常奇怪的问题。我将提供两组代码，我相信它们在理论上都做同样的事情，但提供不同的答案（一个对，一个错）。第一组代码：

def decompose(x, n):
    a = int(((x)//10**(n)))
    b = int(x % (10**(n)))
    #print("a", a, "\t", "b", b)
    return a, b


def digits(x):
    return len(str(x))

# both x and y are n digit numbers


def multiply(x, y):
    n2 = min(digits(x), digits(y))//2
    if x < 10 or y < 10:
        return x*y
    a, b = decompose(x, n2)
    # print("a", a, "\t", "b", b)
    c, d = decompose(y, n2)
    # print("c", c, "\t", "d", d)

    if min(digits(a), digits(b), digits(c), digits(d)) == 1:
        ac = int(a*c)
        bd = int(b*d)
        adbc = int((a+b)*(c+d) - a*c - b*d)
    else:
        ac = multiply(a, c)
        bd = multiply(b, d)
        adbc = multiply(a+b, c+d) - ac - bd

    return (10**(2*n2))*ac + (10**(n2))*(adbc) + bd


x, y = 3141592653589793238462643383279502884197169399375105820974944592, 2718281828459045235360287471352662497757247093699959574966967627
print(multiply(x, y))
print(x*y)

第二组代码：

def decompose(x):
    n = digits(x)
    a = int(((x)//10**(n//2)))
    b = int(x % (10**(n//2)))
    #print("a", a, "\t", "b", b)
    return a, b


def digits(x):
    return int(len(str(x)))

# both x and y are n digit numbers


def multiply(x, y):
    n2 = min(digits(x), digits(y))//2
    if x < 10 or y < 10:
        return x*y
    a, b = decompose(x)
    # print("a", a, "\t", "b", b)
    c, d = decompose(y)
    # print("c", c, "\t", "d", d)

    if min(digits(a), digits(b), digits(c), digits(d)) == 1:
        ac = int(a*c)
        bd = int(b*d)
        adbc = int((a+b)*(c+d) - a*c - b*d)
    else:
        ac = multiply(a, c)
        bd = multiply(b, d)
        adbc = multiply(a+b, c+d) - ac - bd

    return (10**(2*n2))*ac + (10**(n2))*(adbc) + bd


x, y = 3141592653589793238462643383279502884197169399375105820974944592, 2718281828459045235360287471352662497757247093699959574966967627
print(multiply(x, y))
print(x*y)

在第一组中，我通过了 n2，其中 n2 = 32，因为 x 和 y 有 64 位。在这种情况下，我得到了 x 和 y 乘积的正确答案。但是，在第二组代码中，我手动找到位数，然后使用整数除法将其除以 2，这也应该给出 32，但给了我错误的答案。任何帮助，将不胜感激。

4

0 回答 0