Revision of karatsuba multiplication

1 file changed, 28 insertions

karatsuba_multipication.py(file created)

		@@ -0,0 +1,28 @@
1	+	def karatsuba(x: int, y: int) -> int:
2	+	"""Multiply 2 same lenght ints using the karatsuba algorithm"""
3	+	# base case
4	+	if x < 10 or y < 10:
5	+	return x * y
6	+
7	+	# Calculate the number of digits of the larger number
8	+	n = max(len(str(x)), len(str(y)))
9	+	n_2 = n // 2
10	+
11	+	# split in half
12	+	a, b = divmod(x, 10**n_2)
13	+	c, d = divmod(y, 10**n_2)
14	+
15	+	# Recursively compute
16	+	bd = karatsuba(b, d)
17	+	pq = karatsuba((b + a), (d + c))
18	+	ac = karatsuba(a, c)
19	+
20	+	# Combine
21	+	return (ac * 10 ** (2 * n_2)) + ((pq - ac - bd) * 10**n_2) + bd
22	+
23	+
24	+	# test
25	+	x = 9823892839835678
26	+	y = 1239823892839834
27	+	result = karatsuba(x, y)
28	+	print(f"{x} x {y} = {result}")

Newer Older