Karatsuba_negative

mail@pastecode.io avatar
unknown
python
7 months ago
425 B
3
Indexable
Never
def karatsuba(x,y):
  n = max(x.bit_length(), y.bit_length())

  if n < 2:
    return x*y
    
  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(-45952456498465985,-986544651986546519865))