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

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*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).

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*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:])