def karatsuba(x, y): """Function to multiply 2 numbers in a more efficient manner than the grade school algorithm""" if len(str(x)) == 1 or len(str(y)) == 1: return x * y else: n = max(len(str(x)), len(str(y))) nby2 = n / 2
a = x / 10**(nby2) b = x % 10**(nby2) c = y / 10**(nby2) d = y % 10**(nby2)
ac = karatsuba(a, c) bd = karatsuba(b, d) ad_plus_bc = karatsuba(a + b, c + d) - ac - bd
# this little trick, writing n as 2*nby2 takes care of both even and # odd n prod = ac * 10**(2 * nby2) + (ad_plus_bc * 10**nby2) + bd
return prod
if __name__ == "__main__": print(karatsuba(86123457, 12345678))
#! /usr/local/bin/python3.6 """ Multiplication of big-digit values with Toom-Cook 3-way method """ import random import sys import traceback
class MultiplyToomCook3: D_MAX = 729 # Maximum number of digits (power of 3) D = 729 # Digits of computation (<= D_MAX)
def __init__(self): self.a = [random.randrange(10) for _ in range(self.D)] self.b = [random.randrange(10) for _ in range(self.D)]
def compute(self): """ Computation of multiplication """ try: for i in range(self.D_MAX - len(self.a)): self.a.append(0) for i in range(self.D_MAX - len(self.b)): self.b.append(0) z = self.__multiply_toom_cook_3(self.a, self.b) z = self.__do_carry(z) self.__display(self.a, self.b, z) except Exception as e: raise
def __multiply_normal(self, a, b): """ Normal multiplication :param list a :param list b :return list z """ try: a_len, b_len = len(a), len(b) z = [0 for _ in range(a_len + b_len)] for j in range(b_len): for i in range(a_len): z[j + i] += a[i] * b[j] return z except Exception as e: raise
def __multiply_toom_cook_3(self, a, b): """ Toom-Cook 3-way multiplication :param list a :param list b :return list z """ a_m1, a_m2, a_0, a_1, a_inf = [], [], [], [], [] b_m1, b_m2, b_0, b_1, b_inf = [], [], [], [], [] c_m1, c_m2, c_0, c_1, c_inf = [], [], [], [], [] c0, c1, c2, c3, c4 = [], [], [], [], [] try: t_len = len(a) # ９桁（配列９個）になった場合は標準乗算 if t_len <= 9: return self.__multiply_normal(a, b) a0 = a[:(t_len // 3)] a1 = a[(t_len // 3):(t_len * 2 // 3)] a2 = a[(t_len * 2 // 3):] b0 = b[:(t_len // 3)] b1 = b[(t_len // 3):(t_len * 2 // 3)] b2 = b[(t_len * 2 // 3):] for i in range(t_len // 3): a_m2.append((a2[i] << 2) - (a1[i] << 1) + a0[i]) b_m2.append((b2[i] << 2) - (b1[i] << 1) + b0[i]) for i in range(t_len // 3): a_m1.append(a2[i] - a1[i] + a0[i]) b_m1.append(b2[i] - b1[i] + b0[i]) a_0, b_0 = a0, b0 for i in range(t_len // 3): a_1.append(a2[i] + a1[i] + a0[i]) b_1.append(b2[i] + b1[i] + b0[i]) a_inf, b_inf= a2, b2 c_m2 = self.__multiply_toom_cook_3(a_m2, b_m2) c_m1 = self.__multiply_toom_cook_3(a_m1, b_m1) c_0 = self.__multiply_toom_cook_3(a_0, b_0) c_1 = self.__multiply_toom_cook_3(a_1, b_1) c_inf = self.__multiply_toom_cook_3(a_inf, b_inf) c4 = c_inf for i in range((t_len // 3) * 2): c = -c_m2[i] c += (c_m1[i] << 1) + c_m1[i] c -= (c_0[i] << 1) + c_0[i] c += c_1[i] c += (c_inf[i] << 3) + (c_inf[i] << 2) c = c // 6 c3.append(c) for i in range((t_len // 3) * 2): c = (c_m1[i] << 1) + c_m1[i] c -= (c_0[i] << 2) + (c_0[i] << 1) c += (c_1[i] << 1) + c_1[i] c -= (c_inf[i] << 2) + (c_inf[i] << 1) c = c // 6 c2.append(c) for i in range((t_len // 3) * 2): c = c_m2[i] c -= (c_m1[i] << 2) + (c_m1[i] << 1) c += (c_0[i] << 1) + c_0[i] c += (c_1[i] << 1) c -= (c_inf[i] << 3) + (c_inf[i] << 2) c = c // 6 c1.append(c) c0 = c_0 z = c0 + c2 + c4 for i in range((t_len // 3) * 2): z[i + t_len // 3] += c1[i] for i in range((t_len // 3) * 2): z[i + t_len] += c3[i] return z except Exception as e: raise
def __do_carry(self, a): """ Process of carrying :param list a :return list a """ cr = 0
try: for i in range(len(a)): a[i] += cr cr = a[i] // 10 a[i] -= cr * 10 if cr != 0: print("[ OVERFLOW!! ] ", cr) return a except Exception as e: raise
def __display(self, a, b, z): """ Display :param list a :param list b :param list z """ a_len = self.D_MAX b_len = self.D_MAX z_len = self.D_MAX * 2 try: while a[a_len - 1] == 0: if a[a_len - 1] == 0: a_len -= 1 while b[b_len - 1] == 0: if b[b_len - 1] == 0: b_len -= 1 while z[z_len - 1] == 0: if z[z_len - 1] == 0: z_len -= 1 print("a =") for i in reversed(range(a_len)): print(a[i], end="") if (a_len - i) % 10 == 0: print(" ", end="") if (a_len - i) % 50 == 0: print() print() print("b =") for i in reversed(range(b_len)): print(b[i], end="") if (b_len - i) % 10 == 0: print(" ", end="") if (b_len - i) % 50 == 0: print() print() print("z =") for i in reversed(range(z_len)): print(z[i], end="") if (z_len - i) % 10 == 0: print(" ", end="") if (z_len - i) % 50 == 0: print() print() except Exception as e: raise
if __name__ == '__main__': try: obj = MultiplyToomCook3() obj.compute() except Exception as e: traceback.print_exc() sys.exit(1)