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)
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)