def gradeschool_mult(x,y):
if x<10 or y<10: return x*y
x = str(x); y = str(y);
# convert to string of 0/1's, MSB first
n = max(len(x),len(y))
x = "0"*(n-len(x))+x; y = "0"*(n-len(y))+y # add leading zeroes if needed
m = n//2
xtop = int(x[:-m]); xbot = int(x[-m:])
ytop = int(y[:-m]); ybot = int(y[-m:])
return 10**(2*m)*gradeschool_mult(xtop,ytop)+10**m*(gradeschool_mult(xtop,ybot)+gradeschool_mult(xbot,ytop))+gradeschool_mult(xbot,ybot)
print(gradeschool_mult(100,100))
def karatsuba_mult(x,y):
'''Multiply two simlar length integers via karatsuba algorithm.'''
if x<100 or y<100: return x*y
x = str(x); y = str(y);
# convert to string of 0/1's, MSB first
n = max(len(x),len(y))
x = "0"*(n-len(x))+x; y = "0"*(n-len(y))+y # add leading zeroes if needed
m = n//2
xtop = int(x[:-m]); xbot = int(x[-m:])
ytop = int(y[:-m]); ybot = int(y[-m:])
return (10**(2*m)-10**m)*karatsuba_mult(xtop,ytop)+(10**m)*karatsuba_mult(xtop+xbot,ytop+ybot) +(1-10**m)*karatsuba_mult(xbot,ybot)
print(karatsuba_mult(12342323,3464565463)==12342323* 3464565463)
