Construction of algorithms for Parallel Addition

Joint work with Milena Svobodová

An algebraic number $\beta \in \mathbb{C}$ with no conjugate of modulus $1$ can serve as the base of a numeration system $(\beta, \mathcal{A})$ with parallel addition, i.e., the sum of two operands represented in base $\beta$ with digits from $\mathcal{A}$ is calculated in constant time, irrespective of the length of the operands. In order to allow parallel addition, sufficient level of redundancy must be given to the alphabet $\mathcal{A}$.

Here we aim to find parallel addition algorithms on alphabets of the minimal possible size, for a given base. As the complexity of these algorithms becomes quite huge in general, we introduce a so-called Extending Window Method (EWM) – in fact an algorithm to construct parallel addition algorithms. This method can be applied on bases $\beta$ which are expanding algebraic integers, i.e., $\beta$ whose all conjugates are greater than $1$ in modulus.

Implementation of EWM: GitHub ParallelAddition or DOI

Results for selected numeration systems: DOI

Jan Legerský
Assistant professor