Какой лучший способ изменить побитовый алгоритм Карацубы для работы с отрицательными числами? - PullRequest
Новая
       67

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

0 голосов
/ 27 мая 2018

Я написал этот побитовый алгоритм умножения Карацубы.Он не использует строки или math.pow.Это просто рекурсия «разделяй и властвуй», побитовые операции и сложение: 

def karatsuba(x,y):
  n = max(x.bit_length(), y.bit_length())

  if n < 2:
    return x&y

  # split in O(1)
  n = (n + 1) >> 1

  b = x >> n;
  a = x - (b << n);
  d = y >> n;
  c = y - (d << n);

  ac = karatsuba(a, c);
  bd = karatsuba(b, d);
  abcd = karatsuba(a+b, c+d);

  return ac + ((abcd - ac - bd) << n) + (bd << (n << 1));

print(karatsuba(23,24))
print(karatsuba(-29,31))

# 552
# 381

Абсолютно хорошо работает с положительными числами, но, очевидно, -29 * 31 не равно 381.

Чтосамый простой способ решить проблему?

Моя первая идея состояла в том, чтобы сделать число положительным с помощью (~(-29)+1) = 29, сохранить, было ли оно отрицательным или нет, в логическом значении и обработать его в моем выражении возврата, но есть лилучшее (может быть побитовое) решение?

Заранее спасибо

1 Ответ

0 голосов
/ 27 мая 2018

Проблема связана с вашим случаем выхода, в частности x&y возвращает неправильное значение для отрицательных чисел: 

-1 & 1 == 1   # Needs to return -1

Так что вы можете это исправить, протестировав его или просто вернув: 

if n < 2:
    return x*y

Например: 

In []:
print(karatsuba(-29,31))

Out[]:
-899
...