0

我已经在 Python 中实现了 Karatsuba 乘法。

代码和伪代码如下：

def karatsuba(x, y):
    """
    Input: two n-digit positive integers x and y. 
    Output: the product x·y. 
    Assumption: n is a power of 2. (NOT assuming this)

    if n =1  then                   // base case
        compute x·y in one step and return the result
    else 
        a,b := first and second halves of x 
        c,d := first and second halves of y 
        compute p := a + b and q := c + d using grade-school addition 
        recursively compute ac := a·c, bd := b·d, and pq := p·q 
        compute adbc := pqacbd using grade-school addition 
        compute 10n ·ac + 10n/2 ·adbc + bd using grade-school addition and return the result
    """

    str_x = str(x)
    str_y = str(y)
    if len(str_x) == 1 or len(str_y) == 1:
        return x*y
    else:
        n = max(len(str_x), len(str_y))
        n_half = int(n / 2)
        
        a, b = x // 10**n_half, x % 10**n_half
        c, d = y // 10**n_half, y % 10**n_half
        
        p = a + b
        q = c + d
    
        ac = karatsuba(a, c)
        bd = karatsuba(b, c)
        pq = karatsuba(p, q)
        
        adbc = pq - ac - bd
        
        return 10**(2*n_half) * ac + 10**n_half * adbc + bd

当我对非常大的数字进行乘法运算时，我的代码失败了。

这是一个例子：

>>> a = 3141592653589793238462643383279502884197169399375105820974944592
>>> b = 2718281828459045235360287471352662497757247093699959574966967627
>>> mul_karatsuba = karatsuba(a, b)
>>> mul_builtin = a * b
>>> mul_karatsuba == mul_builtin
False
>>> mul_karatsuba
8945653667798941823160787739573304887842903322205621858854691873536479127635014727457078833467629169552143732979528067839403974
>>> mul_builtin
8539734222673567065463550869546574495034888535765114961879601127067743044893204848617875072216249073013374895871952806582723184

我无法找到我的代码到底有什么问题。我已经根据提到的伪代码对所有内容进行了编码。

你能帮我么？

4

0 回答 0