karatsuba_multipication.py
· 666 B · Python
Raw
def karatsuba(x: int, y: int) -> int:
"""Multiply 2 same lenght ints using the karatsuba algorithm"""
# base case
if x < 10 or y < 10:
return x * y
# Calculate the number of digits of the larger number
n = max(len(str(x)), len(str(y)))
n_2 = n // 2
# split in half
a, b = divmod(x, 10**n_2)
c, d = divmod(y, 10**n_2)
# Recursively compute
bd = karatsuba(b, d)
pq = karatsuba((b + a), (d + c))
ac = karatsuba(a, c)
# Combine
return (ac * 10 ** (2 * n_2)) + ((pq - ac - bd) * 10**n_2) + bd
# test
x = 9823892839835678
y = 1239823892839834
result = karatsuba(x, y)
print(f"{x} x {y} = {result}")
| 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}") |