Karazuba Algorithm with arbitrary bases

Question

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

• Gloweye: You're never going to be anywhere near as fast as the builtin integer type. If you want to display as base_x, then you should just build a class that inherits from int, but displays differently, if you care about speed.
• ATW: It's clear that it won't be faster than the builtin multiplication. I just want to implement the algorithm - at maximum speed, for learning purpose.
• Peter Taylor: The most common transliteration of Карацуба is Karatsuba, as used by e.g. Wikipedia. None of the common romanisations transliterate ц as z. The standard alternatives are Karacuba, Karaczuba, Karatsuba, Karatcuba.

Answer 1

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.

• Peter Taylor: zip(reversed(self.digits), reversed(o.digits)) is not equivalent to reversed(zip(self.digits, o.digits)) unless you have a guarantee that len(self.digits) == len(o.digits).
• GZ0: reversed cannot be applied to zip. You mentioned about that a few days ago :)

Answer 2

Adding to the other reviews, here are a few more points.

Outside-class Functions vs. Methods

Here is a long discussion about function and methods. In general, if a function operates only on instances of a class (including its subclasses), it should be a method of that class. In your program, most of the functionality of the three functions decToBase, baseToDec, and karazubaMultiply are closely related to the BN class so it would be more logical to make them methods within the BN class instead.

1. Function decToBase converts an int to a base-b number. This function can become a factory class method (called using BN.<method_name>(...)) and returns a BN object directly rather than a list.

class BN:
 ...
 @classmethod
 def from_int(cls, n: int, base: int) -> "BN":
 # ...
 # compute digits
 # ...
 return cls(digits, base)
# Usage:
# a = BN.from_int(1000, 3)

Note that the type hint -> BN is not supported yet. You need to either use a string as shown above or add from __future__ import annotations at the beginning of your code (only for Python 3.7+, see this post).

2. Function baseToDec transforms a list representing a base-b number to int. The method getDecimalForm delegates all the task to this function. Unless there is a real need to use this function on other lists rather than just the digits from BN instances, it would be more logical to put all the functionality into getDecimalForm. A better way is to override the __int__ method, and then you can just use int(...) to cast BN objects to int.

class BN:
 def __int__(self):
 # Perform computation using self.digits and self.base and return an int
# Usage:
# a = BN(...)
# int_a = int(a) # Cast using int(...), which implicitly calls a.__int__()

3. Function karazubaMultiply receives two ints, converts them to BN objects, performs Karatsuba multiplication, and then converts the objects back to int. Note that the core multiplication part is actually performed on BN objects. Therefore, this part of logic should be really extracted into BN.__mul__:

class BN:
 def __mul__(self, other):
 # Implements Karatsuba algorithm and returns a new BN object

And the remaining part of the logic can be kept in another function:

def multiply_int_karatsuba(num1, num2, base=2**64):
 num1 = BN.from_int(num1, base)
 num2 = BN.from_int(num2, base)
 return int(num1 * num2)

This organization is a lot more logical.

Issues in Algorithm Implementation

1. Padding a.digits and b.digits to the next power of adds quite some performance overhead. For example, if the two numbers both have digit length of 33, padding them would result in two length-64 numbers and triples the amount of computation (since the algorithm has a complexity of \$O(n^{\log_23})\$). The algorithm can work without any padding (see this example). However, you do need to correctly handle addition (for two numbers of different lengths) and the base case (where one of a, b has length 1 while the other can have an arbitrary length) of multiplication.

As a side note, when really needed, an easy way to compute the next power of two for an int n is this:

next_power_of_two = 1 << n.bit_length() # Equilvalent to 2**n.bit_length() but much more efficient

Using log for this task is unnecessary and inefficient.

2. The algorithm itself is recursive, yet the current implementation does not reflect that at all. Therefore, it is not correct.

3. Note that the addition of two numbers can lead to an overflow (see wiki). Therefore, in the __add__ method, the last carry also needs to be carefully handled.

Answer 3

def decToBase(n: int, b: int) -> list:
def baseToDec(n: list, b: int) -> int:

These names reflect a common misconception. int is not inherently decimal. If any named base were appropriate, it would be bin for binary. But it's far more sensible to think of int as being int: either call them int to base and base to int or, IMO better, base compose and base decompose. Python's style guide (PEP8) would prefer you to use base_compose than baseCompose.

---

 for d1, d2 in zip(reversed(self.digits), reversed(o.digits)):
 ...
 return BN(list(reversed(res)), self.base)

Would it make more sense to store the digits in the reversed (little-endian) order, and only reverse them for display purposes?

---

 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)
 n = next2 // 2

Firstly, don't mix types like that. [0] * would be consistent and lead to fewer bugs.

Secondly, why care about powers of two? None of the algebra here requires that. You might as well optimise with

 if a < b:
 a, b = b, a # ensure a >= b
 a, b = BN(a, base), BN(b, base)
 b.digits = [0] * (a.length - b.length) + b.digits
 n = a.length // 2

(Well, actually even that extension of b isn't strictly necessary).

---

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

Why not do the whole thing using BN and arrays? That is, after all, the way you would have to do it in any language where making your own implementation of Karatsuba's algorithm is necessary.

• ATW: Secondly, why care about powers of two? Because the multiplication works recursive and I will split the resulting number again and again - so I'll only have to multiply one-digit numbers. Thanks.
• Peter Taylor: But that doesn't require every split to be perfectly 50/50. Textbooks use powers of 2 because it simplifies the runtime analysis, but if you just want working code it's unnecessary.