An implementation of the Karatsuba algorithm for multiplication

``````

In [110]:

import sys
import math
print (sys.setrecursionlimit(2000))

``````
``````

None

``````
``````

In [191]:

# Tested on same digits numbers.

def multiply(x,y):

#print (len(x) , len(y))

if len(x) < len(y):
z = y
y = x
x = z

if len(x) == len(y) + 1:
y = "0" + y
elif len(y) == len(x) + 1:
x = "0" + x
elif len(x) == 1 and len(y)==1:
return int(x) * int(y)

n = max(len(x), len(y))

half_ = math.ceil(n/2)
#print(n-half_)
a = x[:n-half_]
b = x[-half_:]

#print ("a,b", x, a,b,half_)
#assert int(x) == int(a) * (10**half_) + int(b), (x,a,half_, b, int(a) * (10**half_) + int(b))

c = y[:n-half_]
d = y[-half_:]

#assert int(y) == int(c) * (10**half_) + int(d), (y,c,half_, d, int(c) * (10**half_) + int(d))
#print (x, y , half_,"abcd", a,b, c, d)

ac = multiply(a,c)
print("ac - multiply",a,"*",c,"=", ac)

bd = multiply(b,d)
print("bd - multiply",b,"*",d,"=", bd)

a_b = str(int(a)+int(b))
c_d = str(int(c)+int(d))

#print ("a_b", a_b, c_d)

product = multiply(a_b, c_d)
print("ab-cd - multiply",a_b,"*",c_d,"=", product)

rest = product - ac - bd

print ("ac, rest, bd", ac, rest, bd)
val = (10**(2*half_)) * ac + (10**(half_))*rest + bd

print("xy - multiply",x,"*",y,"=", val)
return val

# Test Cases

x ="9"
y ="2"
result = multiply(x,y)
print("9*2=",result)
assert result == 18, result

x ="11"
y ="10"
result = multiply(x,y)
print("11*10=",result)
assert result == 110, result

x ="52"
y ="15"
result = multiply(x,y)
print("52*15=",result)
assert result == 780, result

x ="200"
y ="100"
result = multiply(x,y)
print("200*100=",result)
assert result == 20000, result

x ="20002"
y ="10000"
result = multiply(x,y)
print("200*10000=",result)
assert result == 200020000, result

x ="200000"
y ="100000"
result = multiply(x,y)
print("200000*100000=",result)
assert result == 20000000000, result

# x = "3141592653589793238462643383279502884197169399375105820974944592"
# y = "2718281828459045235360287471352662497757247093699959574966967627"
# result = multiply(x,y)
# print("result=",result)

``````
``````

9*2= 18
ac - multiply 1 * 1 = 1
bd - multiply 1 * 0 = 0
ab-cd - multiply 2 * 1 = 2
ac, rest, bd 1 1 0
xy - multiply 11 * 10 = 110
11*10= 110
ac - multiply 5 * 1 = 5
bd - multiply 2 * 5 = 10
ab-cd - multiply 7 * 6 = 42
ac, rest, bd 5 27 10
xy - multiply 52 * 15 = 780
52*15= 780
ac - multiply 2 * 1 = 2
ac - multiply 0 * 0 = 0
bd - multiply 0 * 0 = 0
ab-cd - multiply 0 * 0 = 0
ac, rest, bd 0 0 0
xy - multiply 00 * 00 = 0
bd - multiply 00 * 00 = 0
ab-cd - multiply 2 * 1 = 2
ac, rest, bd 2 0 0
xy - multiply 200 * 100 = 20000
200*100= 20000
ac - multiply 2 * 1 = 2
bd - multiply 0 * 0 = 0
ab-cd - multiply 2 * 1 = 2
ac, rest, bd 2 0 0
xy - multiply 20 * 10 = 200
ac - multiply 20 * 10 = 200
ac - multiply 0 * 0 = 0
ac - multiply 0 * 0 = 0
bd - multiply 2 * 0 = 0
ab-cd - multiply 2 * 0 = 0
ac, rest, bd 0 0 0
xy - multiply 02 * 00 = 0
bd - multiply 02 * 00 = 0
ab-cd - multiply 2 * 0 = 0
ac, rest, bd 0 0 0
xy - multiply 002 * 000 = 0
bd - multiply 002 * 000 = 0
ac - multiply 2 * 1 = 2
bd - multiply 2 * 0 = 0
ab-cd - multiply 4 * 1 = 4
ac, rest, bd 2 2 0
xy - multiply 22 * 10 = 220
ab-cd - multiply 22 * 10 = 220
ac, rest, bd 200 20 0
xy - multiply 20002 * 10000 = 200020000
200*10000= 200020000
ac - multiply 2 * 1 = 2
ac - multiply 0 * 0 = 0
bd - multiply 0 * 0 = 0
ab-cd - multiply 0 * 0 = 0
ac, rest, bd 0 0 0
xy - multiply 00 * 00 = 0
bd - multiply 00 * 00 = 0
ab-cd - multiply 2 * 1 = 2
ac, rest, bd 2 0 0
xy - multiply 200 * 100 = 20000
ac - multiply 200 * 100 = 20000
ac - multiply 0 * 0 = 0
ac - multiply 0 * 0 = 0
bd - multiply 0 * 0 = 0
ab-cd - multiply 0 * 0 = 0
ac, rest, bd 0 0 0
xy - multiply 00 * 00 = 0
bd - multiply 00 * 00 = 0
ab-cd - multiply 0 * 0 = 0
ac, rest, bd 0 0 0
xy - multiply 000 * 000 = 0
bd - multiply 000 * 000 = 0
ac - multiply 2 * 1 = 2
ac - multiply 0 * 0 = 0
bd - multiply 0 * 0 = 0
ab-cd - multiply 0 * 0 = 0
ac, rest, bd 0 0 0
xy - multiply 00 * 00 = 0
bd - multiply 00 * 00 = 0
ab-cd - multiply 2 * 1 = 2
ac, rest, bd 2 0 0
xy - multiply 200 * 100 = 20000
ab-cd - multiply 200 * 100 = 20000
ac, rest, bd 20000 0 0
xy - multiply 200000 * 100000 = 20000000000
200000*100000= 20000000000

``````
``````

In [67]:

``````
``````

2000

``````
``````

In [ ]:

``````
``````

In [ ]:

``````