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 $m$ less than $n$

$x=x_{1}B^{m}+x_{0},$

y=y_{1}B^{m}+y_{0},

where $x_{0}$ and $y_{0}$ are less than $B^{m}$ .

The product is then:

$xy=(x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0}),$

xy=z_{2}B^{2m}+z_{1}B^{m}+z_{0},

where:

z_{2}=x_{1}y_{1},

z_{1}=x_{1}y_{0}+x_{0}y_{1},

z_{0}=x_{0}y_{0}.

the last step is the multiplication and subtraction:

z_{1}=(x_{1}+x_{0})(y_{1}+y_{0})-z_{2}-z_{0}.

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

(a+bi)(c+di)=(ac-bd)+(bc+ad)i.

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