Python script to multiply big-digit values with Karatsuba method.

multiply_karatsuba.py

#! /usr/local/bin/python3.6
"""
Multiplication of big-digit values with Karatsuba method
"""
import random
import sys
import traceback


class MultiplyKaratsuba:
    D_MAX = 1024  # Maximum number of digits (power of 2)
    D     = 1024  # Digits of computation (Multiples of 4 <= 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_karatsuba(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_karatsuba(self, a, b):
        """ Karatsuba multiplication

        :param  list a
        :param  list b
        :return list z
        """
        try:
            t_len = len(a)
            if t_len <= 4:
                return self.__multiply_normal(a, b)
            a_0 = a[:(t_len // 2)]
            a_1 = a[(t_len // 2):]
            b_0 = b[:(t_len // 2)]
            b_1 = b[(t_len // 2):]
            v, w = [], []
            for i in range(t_len // 2):
                v.append(a_1[i] + a_0[i])
                w.append(b_1[i] + b_0[i])
            x_1 = self.__multiply_karatsuba(a_0, b_0)
            x_2 = self.__multiply_karatsuba(a_1, b_1)
            x_3 = self.__multiply_karatsuba(v,  w)
            for i in range(t_len):
                x_3[i] -= x_1[i] + x_2[i]
            z = x_1 + x_2
            for i in range(t_len):
                z[i + t_len//2] += x_3[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 = MultiplyKaratsuba()
        obj.compute()
    except Exception as e:
        traceback.print_exc()
        sys.exit(1)