Karatsuba algorithm for fast multiplication in Python
The Karatsuba Algorithm for fast multiplication is a Divide-and-Conquer approach, it has a slightly better Complexity of O(n1.58) over grade-school multiplication which has a complexity of O(n2). This post aims to explain the Karatsuba algorithm for fast multiplication in Python.
Given two numbers m and n. Length of each number = k digits. We want to find the product of these two numbers.
The more lengthy the numbers the more complex it becomes to find out their product.
How The Karatsuba Fast Multiplication Algorithm Works
According to this algorithm, we can represent any number of k digits as m = a*10k/2 + b,
where k is the length of the number.
a and b are decided based on the length of the number.
let m = 3425. so 3425 = 34*10
+ 25 = 34*100 + 25 (m = a*10
+ b) => a = 34 and b = 25
Let n = 2486
so 2486 = 24*104/2 + 86 = 24*100 + 86 (n = c*10k/2 + d)
=> c = 24 and d = 86
so, m*n = (a*10k/2 + b))*(c*10k/2 + d) = (ac) * 10k + (ad + bc)*10k/2 + (bd)
After calculating ac and bd, then (ad + bc) can be calculated by subtracting ac and bd from (a+b)(c+d) which is (ac + bd + ad + bd).
(ac + bd + ad + bd) - ac - bd = (ad + bc)
A simple example in which we will use the Karatsuba algorithm
m = 3425 and n = 2486.
We want to find m*n using Karatusba Multiplication Algorithm.
As discussed above,
a = 34, b = 25
c = 24, d = 86
m*n = (a*10
+ d) = (ac) * 10
+ (ad + bc)*10
+ (bd) => (34*10
+ 86) = (ac) * 10
+ (ad + bc)*10
=> (34*102 + 25))*(24*102 + 86) = (816) * 104 + (ad + bc)*104/2 + (2150)
(We can calculate these smaller multiplications recursively by calling the Kasturba Algorithm again)
Now ad + bc = (ac + bd + ad + bd) – ac – bd = ((a+b) * (c+d))
So, ad + bc = ((34+25) * (24+86)) – 816 – 2150 = (59 * 110) – (2966) = 6490 – 2966 = 3524
So, 3425*2486 = 8160000 + 352400 + 2150 = 8514550
Python Code: Karatsuba algorithm for fast multiplication
Karatsuba algorithm for fast multiplication in Python code:
def karatsuba(m,n): if(m<10 or n<10): return m*n else: mstring = str(m) nstring = str(n) k = max(len(mstring), len(nstring)) mid=int(k/2) #finding a and c i.e. the higher bits for each number a = int(mstring[:-mid]) c = int(nstring[:-mid]) #finding b and d i.e. the lower bits for each number b = int(mstring[-mid:]) d = int(nstring[-mid:]) #finding ac, bd and ad_plus_bc ac = karatsuba(a, c) bd = karatsuba(b, d) ad_plus_bc = karatsuba(a + b, c + d) - ac - bd return ac*10**(2 * mid) + ad_plus_bc*10**(mid) + bd print("Answer is:") print(karatsuba(3425,2486))