在Python中实现Karatsubas乘法算法

Question

我正在尝试在Python中实现Karatsuba的乘法算法

我的代码

import math
# Base
B=10
# No. of digits
n=4
# Numbers
x=1234
y=5678
def karatsuba(x,y,d):
    if (x < 10 o r y < 10):
        return x*y
    # Partition
    m=math.floor(d/2)
    n=math.ceil(d/2)
    x1=x//B**n
    x2=x%B**n
    y1=y//B**n
    y2=y%B**n
    a=karatsuba(x1,y1,m)
    b=karatsuba(x1+x2,y1+y2,m) #Line 25
    c=karatsuba(x2,y2,n)
    tot = a*(B**(2*m)) + b*(B**m) + c
res=karatsuba(x,y,n)
print('%d * %d = %d' %(x, y, res))

但是正如你在Line 25中看到的，当我们执行x1+x2和y1+y2(考虑x1, x2, y1, y2是m位数)时，一个或两个和可能超过m位数。在这种情况下，我如何递归调用karatsuba()与两个数字有不同的位数。有谁能给出简单的解决方法吗?

Answer 1

这应该是我为算法课程做的一个工作实现:

def karatsuba(x, y):
    if x < 10 or y < 10:
        return x * y
    # get longest digits
    n = max(math.log10(x) + 1, math.log10(y) + 1)
    # catch where n is odd
    n -= n % 2
    bn = B ** (n // 2)
    x1, x2 = divmod(x, bn)
    y1, y2 = divmod(y, bn)
    ac = karatsuba(x1, y1)
    bd = karatsuba(x2, y2)
    # caluclate a+b and c + d subtracting already
    # calculated ac and bd leaving ad + bc
    adbc = karatsuba(x1 + x2, y1 + y2) - ac - bd
    # x . y = 10 ^ n ac + 10^n/2 (ad + bc) + bd
    return ((B ** n) * ac) + bn * adbc + bd

res = karatsuba(x, y)
print('%d * %d = %d' % (x, y, res))

Answer 2

你不需要传递数字的大小。如果你这样做，你的算法只适用于每次递归调用中数字相等的数字。相反，在输入函数时，计算两个数字n = max(len(str(x)), len(str(y)))的位数，然后在x, y的最高有效位数末尾加上0，然后将两者除以n/2。