Алгоритм Карацубы, где ошибка?

Question

[redfoo]

Здравствуйте, написал скрипт для умножения по алгоритму Карацубы, но почему то он считает не правильно, помогите найти ошибку

def multi(x, y):
	return int(x) * int(y)
def arr(x, y):
	x = str(x)
	y = str(y)
	n = max(len(x), len(y))
	half_n = n // 2
	x_l = x[:half_n]
	x_r = x[half_n:]
	y_l = y[:half_n]
	y_r = y[half_n:]
	return x_l, x_r, y_l, y_r

def karatsuba(x, y):
	x = str(x)
	y = str(y)
	n = max(len(str(x)), len(str(y)))
	half_n = n // 2
	if n == 1:
		return multi(x, y)
	num_arr = arr(x, y)
	x_l = num_arr[0]
	x_r = num_arr[1]
	y_l = num_arr[2]
	y_r = num_arr[3]
	if x_l == '':
		x_l = 0
	if x_r == '':
		x_r = 0
	if y_l == '':
		y_l = 0
	if y_r == '':
		y_r = 0
	sum_x = (int(x_l) + int(x_r))
	sum_y = (int(y_l) + int(y_r))
	Res1 = karatsuba(x_l, y_l)
	Res2 = karatsuba(x_r, y_r)
	Res3 = karatsuba(sum_x, sum_y)
	trick = int(Res3) - int(Res1) - int(Res2)
	return((pow(10, n) * Res1) + (pow(10, half_n) * (Res3 - Res1 - Res2)) + Res2)

Answer 1

[longclaps]

разбирайся

def multi(x, y):
    return int(x) * int(y)


def karatsuba(x, y):
    x = str(x)
    y = str(y)
    n = max(len(x), len(y))
    if n == 1:
        return multi(x, y)
    half_n = n // 2
    x_l = x[:-half_n]
    x_r = x[-half_n:]
    y_l = y[:-half_n]
    y_r = y[-half_n:]
    if x_l == '':
        x_l = 0
    if x_r == '':
        x_r = 0
    if y_l == '':
        y_l = 0
    if y_r == '':
        y_r = 0
    sum_x = (int(x_l) + int(x_r))
    sum_y = (int(y_l) + int(y_r))
    Res1 = karatsuba(x_l, y_l)
    Res2 = karatsuba(x_r, y_r)
    Res3 = karatsuba(sum_x, sum_y)
    return ((pow(100, half_n) * Res1) + (pow(10, half_n) * (Res3 - Res1 - Res2)) + Res2)

Comments

[redfoo]

Спасибо, но что то не могу понять, почему срезы с минусом и почему в return 100 возводится в степень, не могли бы вы объяснить, если вас не затруднит

[longclaps]

Срезы с минусом, потому что я отрезаю хвосты строк равной длины, а не головы.
100, потому что 10^2 (смотри описание алгоритма, там есть)