Karatsuba_multi

mail@pastecode.io avatar
unknown
python
6 months ago
471 B
1
Indexable
Never
def karatsubaMultiply(x,y):
	if len(str(x)) == 1 or len(str(y)) == 1:
		return x * y
	else:
		n = max(len(str(x)),len(str(y)))
		n_by_2 = n // 2

		a = x // 10**(n_by_2)
		b = x % 10**(n_by_2)
		c = y // 10**(n_by_2)
		d = y % 10**(n_by_2)

		ac = karatsubaMultiply(a,c)

		bd = karatsubaMultiply(b,d)

		ad_bc = karatsubaMultiply(a+b,c+d) - ac - bd

		finalAns = ac * 10**(2*n_by_2) + ad_bc * 10**(n_by_2) + bd

		return finalAns

x = 
y = 
print(karatsubaMultiply(x,y))