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(n^1.58) over grade-school multiplication which has a complexity of O(n²). 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*10^k/2 + b,

where k is the length of the number.

a and b are decided based on the length of the number.

For example,

let m = 3425.

so 3425 = 34*10

^4/2

 + 25 = 34*100 + 25        (m = a*10

^k/2

 + b)

=> a = 34 and b = 25

Let n = 2486

so 2486 = 24*10^4/2 + 86 = 24*100 + 86        (n = c*10^k/2 + d)

=> c = 24 and d = 86

so, m*n = (a*10^k/2 + b))*(c*10^k/2 + d) = (ac) * 10^k + (ad + bc)*10^k/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).

Clearly,

(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

^k/2

 + b))*(c*10

^k/2

 + d) = (ac) * 10

^k

 + (ad + bc)*10

^k/2

 + (bd)
=> (34*10

^4/2

 + 25))*(24*10

^4/2

 + 86) = (ac) * 10

⁴

 + (ad + bc)*10

^4/2

 + (bd)

=> (34*10² + 25))*(24*10² + 86) = (816) * 10⁴ + (ad + bc)*10^4/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))

Output:

 

Also Read: Count number of leading spaces in a string in Python