Karatsuba_negative
unknown
python
2 years ago
425 B
7
Indexable
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))
Editor is loading...