What's the best way to modify a bitwise Karatsuba-Algorithm to work with negative numbers?

Question

I wrote this bitwise Karatsuba multiplication algorithm. It does not use strings or math.pow. It's just divide-and-conquer-recursion, bitwise operations and addition:

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

It works absolutly fine with positive numbers, but obviously -29*31 is not equal 381.

What's the easiest way to fix the problem?

My first idea was to make the number positive with (~(-29)+1) = 29, store wheather it was negative or not in a boolean and handle that boolean in my return statement, but is there a better (maybe bitwise) solution?

Thanks in advance

Answer 1

The issue is with your exit case, in particular x&y returns the wrong value for negative numbers:

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

So you can fix this with testing for it or or just returning:

if n < 2:
    return x*y

E.g.:

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

Out[]:
-899