Mdthbs

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) -> 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) -> 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 < b:

        a, b = b, a # ensure a >= 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(zip(self.digits, o.digits))

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.