TheAlgorithms-Python

1
"""Multiply two numbers using Karatsuba algorithm"""
2

3

4
def karatsuba(a: int, b: int) -> int:
5
    """
6
    >>> karatsuba(15463, 23489) == 15463 * 23489
7
    True
8
    >>> karatsuba(3, 9) == 3 * 9
9
    True
10
    """
11
    if len(str(a)) == 1 or len(str(b)) == 1:
12
        return a * b
13

14
    m1 = max(len(str(a)), len(str(b)))
15
    m2 = m1 // 2
16

17
    a1, a2 = divmod(a, 10**m2)
18
    b1, b2 = divmod(b, 10**m2)
19

20
    x = karatsuba(a2, b2)
21
    y = karatsuba((a1 + a2), (b1 + b2))
22
    z = karatsuba(a1, b1)
23

24
    return (z * 10 ** (2 * m2)) + ((y - z - x) * 10 ** (m2)) + (x)
25

26

27
def main():
28
    print(karatsuba(15463, 23489))
29

30

31
if __name__ == "__main__":
32
    main()
33