karatsuba Algorithm
Cook algorithm (1963) is a faster generalization of Karatsuba's method, and the Schönhage – Strassen algorithm (1971) is even faster, for sufficiently large N. The Karatsuba algorithm is a fast multiplication algorithm. The article had been write by Kolmogorov and contained two outcomes on multiplication, Karatsuba's algorithm and a separate consequence by Yuri Ofman; it listed" A. Karatsuba and Yu.
In 1960, Kolmogorov organized a seminar on mathematical problems in cybernetics at the Moscow state University, where he stated the Ω. Kolmogorov gave some lectures on the Karatsuba consequence at conferences all over the universe (see, for example," proceedings of the International Congress of Mathematicians 1962", pp.
""" Multiply two numbers using Karatsuba algorithm """
def karatsuba(a, b):
"""
>>> karatsuba(15463, 23489) == 15463 * 23489
True
>>> karatsuba(3, 9) == 3 * 9
True
"""
if len(str(a)) == 1 or len(str(b)) == 1:
return a * b
else:
m1 = max(len(str(a)), len(str(b)))
m2 = m1 // 2
a1, a2 = divmod(a, 10 ** m2)
b1, b2 = divmod(b, 10 ** m2)
x = karatsuba(a2, b2)
y = karatsuba((a1 + a2), (b1 + b2))
z = karatsuba(a1, b1)
return (z * 10 ** (2 * m2)) + ((y - z - x) * 10 ** (m2)) + (x)
def main():
print(karatsuba(15463, 23489))
if __name__ == "__main__":
main()
