Karazuba Algorithm with arbitrary bases I'm working on an implementation of the Karazuba Algorithm. I created a class  BN which represents a number in an arbitrary base (and supports elementary operations). The algorithm works - but I'm not sure if I complicated it. Is there a better way to implement it or a way to optimize the code?

def decToBase(n: int, b: int) -&gt; list:
    if n == 0:
        return [0]
    digits = []
    while n:
        digits.append(int(n % b))
        n //= b
    return list(reversed(digits))

def baseToDec(n: list, b: int) -&gt; int:
    res = 0
    for index, i in enumerate(reversed(n)):
        res += int(i) * b ** index
    return res

from math import log2, ceil, log10, floor

class BN(): # Base Number
    def __init__(self, num, base):
        if type(num) == list:
            self.digits = num
        else:
            self.digits = decToBase(num, base)
        self.base = base
        self.length = len(self.digits)

    def __add__(self, o):
        if self.base != o.base:
            raise ValueError("base of summands must be equal")
        carry = 0
        res = []
        for d1, d2 in zip(reversed(self.digits), reversed(o.digits)):
            s = int(d1) + int(d2) + carry
            res.append(str(s % self.base))
            carry = s // self.base
        return BN(list(reversed(res)), self.base)

    def __mul__(self, o):
        # implementation pending
        return BN(decToBase(self.getDecimalForm() * o.getDecimalForm(), self.base), self.base)

    def __sub__(self, o):
        # implementation pending
        return BN(decToBase(self.getDecimalForm() - o.getDecimalForm(), self.base), self.base)

    def getDecimalForm(self):
        return baseToDec(self.digits, self.base)

def karazubaMultiply(a, b, base=2**64):
    if a &lt; b:
        a, b = b, a # ensure a &gt;= b
    next2 = 2 ** ceil(log2(floor(log10(a))+1)) # next power of 2
    a, b = BN(a, base), BN(b, base)
    a.digits, b.digits = ['0'] * (next2 - a.length) + a.digits, ['0'] * (next2 - b.length) + b.digits
    n = next2 // 2
    x2, x1 = BN(a.digits[:n], base), BN(a.digits[n:], base)
    y2, y1 = BN(b.digits[:n], base), BN(b.digits[n:], base)
    p1, p2, p3 = x2 * y2, x1 * y1, (x1 + x2) * (y1 + y2)
    p1, p2, p3 = p1.getDecimalForm(), p2.getDecimalForm(), p3.getDecimalForm()

    xy = p1 * base ** (2*n) + (p3 - (p1 + p2)) * base ** n + p2

    return xy
Combine division and modulus

Use https://docs.python.org/3/library/functions.html#divmod

rather than this:

    digits.append(int(n % b))
    n //= b


Replace loop with sum

This

res = 0
for index, i in enumerate(reversed(n)):
    res += int(i) * b ** index
return res


is a good candidate for conversion to a generator, i.e.

return sum(int(i) * b**index for index, i in enumerate(reversed(n)))


However, you can get rid of that reversed if you change the power index to be len(n) - index.

Imports at the top

Move this:

from math import log2, ceil, log10, floor


to the top of your file.

Don't compare types

Rather than this:

if type(num) == list:


use isinstance.

Member mutability

You shouldn't care that num is coming in as a list; you should only check that it's iterable. And store it as a tuple, not a list, because you don't (and shouldn't) mutate it in your class code.

Call reversed once

This:

zip(reversed(self.digits), reversed(o.digits))


should be

reversed(tuple(zip(self.digits, o.digits)))


The inner tuple is required because reversed does not accept an iterator.

Don't use strings for math

Just don't. This:

a.digits, b.digits = ['0']


is not a good idea. Use actual digits whenever possible, and it is possible here.