Karatsuba algorithm – O(n^2) becomes O(n^1.58)

The Karatsuba algorithm is a fast multiplication algorithm of two (works better for large) n-digit numbers(x and y),using three multiplications of smaller numbers(about half as many digits as x or y), plus some additions and digit shifts.

The steps are:

For any positive integer  less than  (string length):

where   and   are less than  .

The product is then:

where:

the last step is the multiplication and subtraction:

This is easily done in a recursive way by using Gauss’s complex multiplication algorithm replacing i with the base(m).

import math
def multiply_karatsuba_recursive(x,y):
	strx= str(x)
	stry= str(y)
	nx= len(strx)
	ny= len(stry)
	if nx<=2 or ny<=2: 
            r = int(x)*int(y) 
            return r 
        n = nx 
        if nx>ny:
	    stry= stry.rjust(nx,"0")
	    n=nx
	elif ny>nx:
	    strx= strx.rjust(ny,"0")
	    n=ny
	m = n%2
	offset = 0
	if m != 0:
	   n+=1
	   offset = 1
	floor = int(math.floor(n/2)) - offset
	a = strx[0:floor]
	b = strx[floor:n]
	c = stry[0:floor]
	d = stry[floor:n]
	print(a,b,c,d)
	ac = multiply(a,c)
	bd = multiply(b,d)

	ad_bc = multiply_karatsuba_recursive((int(a)+int(b)),(int(c)+int(d)))-ac-bd
        r = ((10**n)*ac)+((10**(n/2))*ad_bc)+bd

        return r