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
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
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