# Implementing Karatsuba Multiplication Algorithm in Python

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 == "1") and not signed) or (input_data == "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 == "1" ) ^ ( multiplier.bin == "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


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" or
(input_data == "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 .

• Removing - in the else block should be unnecessary since bypassing the elif block proves that input_data doesn't contain one. – David Harkness Jul 28 '14 at 22:19
• @DavidHarkness - Absolutely right. Just was copying his code and missed that redundant step. – dr jimbob Jul 29 '14 at 5:05
• +1 For internal helper function ! The unnecessary overhead was the thing that kept itching my brain ... ! Overall a great answer ! Thanks a lot :) – Raghav RV Jul 29 '14 at 15:29
• Looks like BitArray requires tinkering with the __new__ to be subclassed ! – Raghav RV Jul 29 '14 at 21:11
• @rvraghav93 - Completely right. This is what happens when you subclass other's code without testing and neglect the allocation (at __new__) steps which check for different parameters than you provided. Modified the code back to a simple function. – dr jimbob Jul 30 '14 at 3:45