R
R
redfoo2018-05-20 15:33:43
Python
redfoo, 2018-05-20 15:33:43

Karatsuba's algorithm, where is the error?

Hello, I wrote a script for multiplication using the Karatsuba algorithm, but for some reason it does not count correctly, help me find the error

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 the question

In order to leave comments, you need to log in

1 answer(s)
L
longclaps, 2018-05-20
@redfoo

figure it out

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)

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question