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 [ ]: