Implementing Karatsuba Multiplication Algorithm in Python

Question

I am trying to implement Karatsuba multiplication algorithm for binary (base 2) numbers.

A requirement is that the intermediate / final results must also be in binary so as to assist in educative purposes.

This is my implementation so far. (I am using bittstring library as a container for binary digits)

Convertion to BitArray:

This class is created so that signed (2's complement represented binary strings) as well as unsigned / Python signed binary (-0b111) can all be converted to BitArray quickly without handling the same at the spot of usage.

Could this be improved further to make it faster and cleaner?

class BitTools(object):

    # DEV NOTE : BitArray is the class name so pep8 naming ( bit_array ) is
    # not used

    @staticmethod
    def to_BitArray(input_data, bits, signed=False):
        """
        Returns a bit array object, from the input_data.
        """
        result = None

        if type(input_data) not in [str, int, BitArray]:
            raise TypeError(
                "Input must be given as integer or binary strings or bitarray objects")

        # Convert to Bit Array Objects
        if isinstance(input_data, int):
            result = BitArray(int=input_data, length=bits)
            # Sign is taken care by the sign of input_data

        elif isinstance(input_data, str):
            # Sign is decided by the "signed" parameter or - in the input_data
            # string

            input_data = input_data.replace("0b", "")

            if len(input_data) == 0:
                return BitArray(int=0, length=bits)


            # First priority to - in the string "-0b111" ( -7 )
            if "-" in input_data or ((input_data[0] == "1") and not signed) or (input_data[0] == "0"):
                result = BitArray(int=int(input_data, 2), length=bits)

            # Next priority to 2s complement signed binary explicitly mentined
            # as signed
            else:
                input_data = input_data.replace("-", "")
                length = len(input_data)
                mask = int(("1" * length), 2)
                input_data = (int(input_data, 2) ^ mask) + 1
                result = BitArray(int=-input_data, length=bits)

        else:
            raise TypeError(
                "Input  must be given as binary strings or integers.")

        return result

Karatsuba Multiplication Algorithm.

class Multipliers(object):

    """
    This class implements various types of mulipliers using different algorithms used in study, analysis
    or practical implementation of ALU's in various Computer architectures.
    """
    @staticmethod
    def karatsuba_multiply(multiplier, multiplicand, bits = None, signed=False):

        # Use bit array only to calculate 2's complement of signed binaries.

        if bits is None:
            multiplier = multiplier.replace('0b','')
            if not signed:
                multiplier = multiplier.lstrip("0")

            multiplicand = multiplicand.replace('0b','')
            if not signed:
                multiplicand = multiplicand.lstrip("0")
            bits = max(len(multiplier), len(multiplicand)) + 1

        len_input = bits

        if (bits % 2) == 0:
            bits += 1

        multiplicand = BitTools.to_BitArray(multiplicand, bits, signed)
        multiplier = BitTools.to_BitArray(multiplier, bits, signed)

        sign_bit = None

        if ( signed or (multiplicand.int < 0) or (multiplier.int < 0)):
            # Calculating the sign of the product
            if ( ( multiplicand.bin[0] == "1" ) ^ ( multiplier.bin[0] == "1" ) ):
                sign_bit = 1
            else:
                sign_bit = 0

            # Strip off the sign bit
            multiplicand.int = abs(multiplicand.int)
            multiplier.int = abs(multiplier.int)

        # Binary without the sign bit
        multiplier_abs = multiplier.bin[1:]
        multiplicand_abs = multiplicand.bin[1:]

        if len(multiplier_abs) == 0 or len(multiplicand_abs) == 0:
            return "0"

        # Base case of 1 bit multiplication
        if len(multiplier_abs) == 1:
            return "1" if ( multiplier_abs == "1" and multiplicand_abs == "1" ) else "0"

        # Base case for 2 bit multiplication
        if len(multiplier_abs) == 2:
            return bin( multiplicand.int * multiplier.int ).replace("0b","")

        m = (bits-1) / 2

        # x = x1*(2**m) + x0
        # y = y1*(2**m) + y0

        x1 = multiplicand_abs[:m]
        x0 = multiplicand_abs[m:]

        y1 = multiplier_abs[:m]
        y0 = multiplier_abs[m:]

        #print x1, x0
        #print y1, y0
        #print "m ", m

        # Upper half of the bits
        z2 = Multipliers.karatsuba_multiply(x1, y1)
        # Lower half of the bits
        z0 = Multipliers.karatsuba_multiply(x0, y0)
        # ( x1 + x0 )( y1 + y0 )
        sum_term1 = int(x1,2) + int(x0,2)
        sum_term1 = bin(sum_term1)

        sum_term2 = int(y1,2) + int(y0,2)
        sum_term2 = bin(sum_term2)

        #print "sum terms: ", sum_term1.replace('0b',''), sum_term2.replace('0b','0')

        z1 = Multipliers.karatsuba_multiply(sum_term1, sum_term2)
        z1 = bin ( int(z1,2) - int(z2,2) - int(z0,2) )
        #print "z1: ", z1

        # The "0" padding at the right is binary equivalent of left shift or muliply with 2**bits
        abs_result = int((z2 + "0"*(2*m)),2) + int((z1 + "0"*(m)),2) + int(z0,2)

        # len_result = 2*length of multiplicand / multiplier

        len_result = 2*len_input

        # Converting to binary of 2ce the bit length of inputs
        abs_result = BitTools.to_BitArray(abs_result, len_result)

        if sign_bit == 1:
            abs_result.int *= -1

        return abs_result.bin

Answer 1

In Python, there's no reason to have to_BitArray as a staticmethod in an otherwise empty BitTools class, when it could just exist as a function. I'd put a set of related functions together in an appropriate python module versus group the functions in a class that is otherwise not used. Static methods inside a class are great when there actually is a meaningful class (e.g., that will have instantiated objects containing member data) and then you functions that are appropriately tied to the class, but don't depend on any specific object.

I'd probably name the function to_bitarray or to_bit_array or create_bit_array to be more consistent (yes I understand your rationale, but typically in python function names lose the capitalization present in their class names).

(Another alternative would be to create a MyBitArray class that inherits from bitstring.BitArray that uses your custom constructor (to_bitarray). Granted this may be more work then its worth.) So I'd write a function like:

from bitstring import BitArray

def create_bit_array(input_data, bits, signed=False):
    if not isinstance(input_data, (int, long, str, unicode, BitArray)):
        raise TypeError("Input must be given as binary strings or integers.")
    elif isinstance(input_data, BitArray):
        return input_data 
    elif isinstance(input_data, (str, unicode)):
        input_data = input_data.replace("0b", "")
        if len(input_data) == 0:
            input_data = 0
        elif ("-" in input_data or input_data[0] == "0" or 
              (input_data[0] == "1" and not signed)):
            input_data = int(input_data, 2)
        else:
            mask = int(("1" * len(input_data)), 2)
            input_data = -1*((int(input_data, 2) ^ mask) + 1)
    return BitArray(int=input_data, length=bits)

should work. Comments are nice, but removed here for conciseness.

You should note I cleaned up the code significantly. First, its redundant to check and raise an Error at the beginning and end if all instance are appropriately handled. You should also note assuming python 2 that isinstance(x, int) evaluates to false for large integers, which belong to the long class. Similarly, it makes sense to treat unicode like strings too. Note, for conciseness I only call the constructor to BitArray once and just modify input_data as necessary.

---

Similarly for karatsuba_multiply I would not put as a staticmethod inside a function, when doing def karatsuba_multiply(...) at top level of an appropriate module is cleaner and easier to use.

Anyhow, I may review further, but overall it seems reasonable.

You probably won't get great performance compared to other languages as recursion is fairly expensive in python. You also seem to be doing significant steps in each recursive call of the form of the input to check and convert it to an appropriate form, which adds a lot of unnecessary overhead.

A better paradigm would be to define a function that is initially called and takes a wide-variety of initial input (from a variety of forms) and deals with annoyances like returning back sign at the outer layer.

This function then cleans it up, and the calls an internal helper function __karatsuba_multiply(x, y, bits) where x and y are already in the appropriate form, so it doesn't have to do any checks/conversions. You can also calculate the bits on each of the recursive multiplications from the previous step .