1

我对编程比较陌生，并且不希望在运行时间方面对该算法特别有效，而只是尝试复制 Karatsuba 算法并使其工作。

我已经尝试了许多数字和小数字（如 y = 40004009343254，x = 40004001343234）工作正常，当数字大小增加时（如 y = 4000400934325423423，x = 4000400134323432423），算法停止正常工作并返回相似但不正确答案。

任何关于可能出错的线索将不胜感激！

注意：这个线程不是关于效率，而是关于获得正确的结果。也就是说，关于效率的评论也会被考虑和赞赏。

代码：

y = 4000400934325423423
x = 4000400134323432423

def firsthalf(array):
    firsthalf = array[:len(array)/2]
    return firsthalf
def secondhalf(array):
    secondhalf = array[len(array)/2:]
    return secondhalf
def arrayjoint(array):
    jointarray = long(''.join(map(str,array)))
    return jointarray
def karatsuba(x,y):
    if len(str(x)) == 0 or len(str(y)) == 0:
        return "Can't multiply by a NULL value!"
    if x < 10 or y < 10:
        return x * y
    x_array = [long(i) for i in str(x)]
    y_array = [long(i) for i in str(y)]
    firsthalf_xarray = firsthalf(x_array)
    secondhalf_xarray = secondhalf(x_array)
    firsthalf_yarray = firsthalf(y_array)
    secondhalf_yarray = secondhalf(y_array)
    half_size = max(len(secondhalf_yarray), len(secondhalf_xarray))
    firsthalf_x = arrayjoint(firsthalf_xarray)
    secondhalf_x = arrayjoint(secondhalf_xarray)
    firsthalf_y = arrayjoint(firsthalf_yarray)
    secondhalf_y = arrayjoint(secondhalf_yarray)
    sum_x = firsthalf_x + secondhalf_x
    sum_y = firsthalf_y + secondhalf_y
    first = karatsuba(firsthalf_x,firsthalf_y)
    second = karatsuba(sum_x, sum_y)
    third = karatsuba(secondhalf_x,secondhalf_y)
    return first * 10 ** (2 * half_size) + ((second - first - third) * (10 ** half_size)) + third

result = karatsuba(x,y)
result_correct = x*y
result = str(result)
result_correct = str(result_correct)
file = open("result.txt", "w")
file.write(str(result)  + "\n" + str(result_correct))
file.close
4

1 回答 1

1

浮点数不是问题，因为 Python 有 bignums。

问题在于，当输入具有不同的长度时，您会将它们拆分到不同的位置，这会破坏 Karatsuba 算法的代数。通过在索引处拆分-half_size（即后半部分有half_size数字），我们确保这10**half_size是正确的基础。尝试这个：

def digits_to_long(x_array):
    return long(''.join(x_array)) if x_array else 0L


def karatsuba(x, y):
    if x < 10 or y < 10:
        return x * y
    x_array = str(x)
    y_array = str(y)
    half_size = max(len(x_array), len(y_array)) // 2
    firsthalf_x = digits_to_long(x_array[:-half_size])
    secondhalf_x = digits_to_long(x_array[-half_size:])
    firsthalf_y = digits_to_long(y_array[:-half_size])
    secondhalf_y = digits_to_long(y_array[-half_size:])
    sum_x = firsthalf_x + secondhalf_x
    sum_y = firsthalf_y + secondhalf_y
    first = karatsuba(firsthalf_x, firsthalf_y)
    second = karatsuba(sum_x, sum_y)
    third = karatsuba(secondhalf_x, secondhalf_y)
    return first * 10**(2 * half_size) + (
        (second - first - third) * (10**half_size)) + third


import random
for i in range(10000):
    x = random.randrange(10**18)
    y = random.randrange(10**18)
    assert karatsuba(x, y) == x * y
于 2016-12-09T15:50:34.973 回答