Karatsuba算法适用于小数而不适用于大数，看不出为什么 [英] Karatsuba algorithm working for small numbers but not for big ones, can't see why

问题描述

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

I am relatively new to programming and am not looking to be particularly efficient with this algorithm regarding running time but only trying to replicate the Karatsuba algorithm and make it work.

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

I have tried it with many numbers and small numbers (like y = 40004009343254, x = 40004001343234) work fine and when the numbers increase in size (like y = 4000400934325423423, x = 4000400134323432423), the algorithm stops working correctly and returns similar but incorrect answers.

任何有关可能出问题的线索将不胜感激！

Any clue about what could be wrong would be very much appreciated!

注意：该主题与效率无关，而与获得正确结果有关。也就是说，对效率的评论也将被考虑和赞赏。

NOTE: This thread is not about efficiency but about getting the correct result. That said, comments about efficiency will be taken into account and appreciated too.

代码：

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

推荐答案

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

It's not an issue with floats, because Python has bignums.

问题是，当输入的长度不同时，可以将它们拆分到不同的位置，它击败了Karatsuba算法基础的代数。通过按索引 -half_size 进行拆分（即，下半部分具有 half_size 位数字），我们确保 10 ** half_size 是适当的基数。试试这个：

The issue is that, when the inputs have disparate lengths, you split them in different places, which defeats the algebra underlying Karatsuba's algorithm. By splitting at index -half_size (i.e., the second half has half_size digits), we ensure that 10**half_size is the proper base. Try this:

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

这篇关于Karatsuba算法适用于小数而不适用于大数，看不出为什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！