# 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^{2}). 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

^{4}

+ (ad + bc)*10

^{4/2}

+ (bd)

=> (34*10^{2} + 25))*(24*10^{2} + 86) = (816) * 10^{4} + (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

## Leave a Reply