In an effort to fill my knowledge on algorithm, I recently watched 1. Integer Arithmetic, Karatsuba Multiplication

What is the Karatsuba Algorithm?

a classic divide and conquer algorithm

from Karatsuba algorithm wiki page,

x = a* B^m + b

y = c* B^m + d

x * y = B^2m(ac) + B^m(ad+bc) + bd

Now, instead of multiplying 1234 x 5678 the long way, you can do this:

a = 12
b = 34
c = 56
d = 78
n = 4
base of 10
x * y = 10^n(ac) + 10^(n/2)(ad + bc) + bd
x * y = 10^4 * (672) + 10^2 * (2840) + 2652
x * y = 7006652

Karatsuba’s basic step works for any base B and any m, but the recursive algorithm is most efficient when m is equal to n/2, rounded up.

To elucidate, for integers with n digits, m is the ceiling of half n (m being the exponent applied to the Base in the algorithm). This can be seen if you simply look at the definition of the algorithm.

In particular, if n is 2^k, for some integer k, and the recursion stops only when n is 1, then the number of single-digit multiplications is 3^k, which is n^c where c = log3

some derivation details

n = 2^k
=> logn = log2^k
=> logn = k * log2
=> logn = k

Verify n^log3 = 3^logn
Define x = n^log3
=> logx = log3 * logn
=> logx = logn * log3
=> logx = log3^logn
hence x = 3^logn and we get 3^logn = n^log3

for n digit number,

T(n) = n^c = 3^k = 3^logn
=> T(n) = n^log3
and c = log3 = 1.585

Python code

def karatsuba(num1, num2):
    if len(str(num1)) == 1 or len(str(num2)) == 1:
        return num1 * num2
    else:
        # Calculates the size of the numbers
        m = max(len(str(num1)), len(str(num2)))
        m2 = m // 2

        # Split the digit sequences in the middle
        high1 = num1//10**m2
        low1 = num1%10**m2
        high2 = num2//10**m2
        low2 = num2%10**m2

        # 3 calls made to numbers approximately half the size.
        z0 = karatsuba(low1, low2)
        z1 = karatsuba((low1 + high1), (low2 + high2))
        z2 = karatsuba(high1, high2)

        return (z2 * 10 ** (2**m2)) + ((z1 - z2 - z0) * 10 ** m2) + z0

More information, please refer to Karatsuba Multiplication Stanford University Coursera