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[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("-", "")

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 .

StackExchange Code Review Q#58184, answer score: 4