Karatsubaアルゴリズムは、小さなものではあるが大きなものではなく、なぜかわからない

Question

私は比較的プログラミングに新しいので、実行時間に関してこのアルゴリズムでは特に効率的であるとは思っていませんが、Karatsubaアルゴリズムを複製し、それは働く。

は 私は多くの数字と小さな数字でそれを試してみました

（Yのような= 40004009343254、 X = 40004001343234）が正常に動作し、（Y = 4000400934325423423のように、X = 4000400134323432423）サイズの数字の増加は、アルゴリズムが停止したときに正しく動作します類似しているが間違った答えを返します。

何が間違っているかについての手がかりは非常に高く評価されます。

注：：このスレッドは効率性についてではなく、正しい結果を得ることについてです。つまり、効率性についてのコメントは考慮され、評価されます。

CODE：

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 

Answer 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