1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def karatsuba(x,y):
    if x < 10 or y < 10:
        return x*y
    else:
        n = max(len(str(x)),len(str(y)))
        mid = int(n/2) 
        power = 10**mid

        a = x // power
        b = x % power
        c = y // power
        d = y % power

        print(a, b, c, d)

        ac = karatsuba(a,c)
        bd = karatsuba(b,d)

        acpbd = karatsuba(a+b,c+d) - ac - bd
        return ac*(power**2) + bd + (acpbd*power)