VOL2018ISSNUMSUBM

# Construction of Algorithms for Parallel Addition

Jan Legerský1,2  Milena Svobodová2  Research Institute for Symbolic
Computation, Johannes Kepler University Linz, Austria
Faculty of Nuclear Sciences and Physical Engineering, Czech Technical
University in Prague, Czech Republic

###### Abstract

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}$. The complexity of
parallel addition algorithm depends heavily on the size $\\#\mathcal{A}$ of
the alphabet: the bigger alphabet is considered, the lower complexity of the
parallel addition algorithm may be reached, and vice versa.
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. Convergence of
the EWM is not guaranteed, nevertheless, we have developed tools for revealing
non-convergence, and there is a number of successful applications. Firstly,
the EWM provides the same parallel addition algorithms as were previously
introduced by A. Avizienis, C.Y. Chow & J.E. Robertson or B. Parhami for
integer bases and alphabets. Then, by applying the EWM on selected complex
bases $\beta$ with non-integer alphabets
$\mathcal{A}\subset\mathbb{Z}[\beta]$, we obtain new results – parallel
addition algorithms on alphabets of minimal possible size, which could not be
found so far (manually). The EWM is helpful also in the case of block parallel
addition.

###### keywords:

complex numeration system, parallel addition, local function, expanding base,
minimal alphabet

##  1 Introduction

Numeration systems $(\beta,\mathcal{A})$ are defined by a base $\beta$
(sometimes also called a radix) and an alphabet $\mathcal{A}$ – the set of
digits. Usually, the base is greater than $1$ in modulus: $|\beta|>1$. A
number $x$ is said to have a representation in the numeration system
$(\beta,\mathcal{A})$, if there exist digits $x_{j}$ from the alphabet
$\mathcal{A}$ such that $x=\sum_{j=r}^{l}x_{j}\beta^{j}$, with
$l\in\mathbb{Z}$ and $r\in(\mathbb{Z}\cup\\{-\infty\\})$. The
$(\beta,\mathcal{A})$-representation of $x$ is then denoted by the string
$(x_{l}\cdots x_{0}\raisebox{0.43057pt}{{.}}x_{-1}\cdots)_{\beta}$, and it may
not be unique.

Our goal is to find those numeration systems $(\beta,\mathcal{A})$ that allow
parallel addition, i.e., where the operation of adding two numbers having
$(\beta,\mathcal{A})$-representations has constant time complexity, assuming
that arbitrary number of operations can be run in parallel. This concept was
introduced by A. Avizienis in [1], and then was intensively elaborated and
brought into practice – not just for the sake of the addition operation
itself, but also as part of other calculations (e.g. fast algorithms for
multiplication or division). In practice, we actually consider only summands
with finite $(\beta,\mathcal{A})$-representations as the operands of addition
algorithms.

When approaching the problem of parallel addition, we start by identifying the
bases $\beta$ for which parallel addition is possible at all, in a broad scope
– so not only integer, but also real and complex bases. The requirement to
allow parallel addition forces the base to be an algebraic number (when
considering $\mathcal{A}\subset\mathbb{Z}$ or
$\mathcal{A}\subset\mathbb{Z}[\beta]$). Existence of parallel addition
algorithm for a given base depends on the fact whether any of its algebraic
conjugates is of modulus equal to $1$ – if not, then parallel addition
algorithms exist for that base (with a suitably chosen alphabet
$\mathcal{A}$). But if $\beta$ has any algebraic conjugate equal to $1$ in
modulus, then parallel addition in base $\beta$ is impossible.

In the second step, given a base $\beta$ suitable for parallel addition, we
focus on the alphabet $\mathcal{A}$. In principle, the more elements in the
alphabet, the better chances for the numeration system $(\beta,\mathcal{A})$
to allow parallel addition – as the redundancy increases, and it is the
redundancy that makes parallel addition possible. In [4], a constructive
method is provided, describing how to choose the alphabet $\mathcal{A}$ (of
consecutive integers, containing $0$, and symmetric), and then how to perform
parallel addition in thus obtained numeration system $(\beta,\mathcal{A})$.
The approach used there consists in finding a
$(\beta,\mathcal{A})$-representation of zero with one dominant digit, i.e.,
strictly greater than the sum of moduli of all the other digits. Such
representation of zero then serves as the core rewriting rule within the
parallel addition algorithm, and also determines the size of the alphabet
$\mathcal{A}\subset\mathbb{Z}$.

The drawback of this approach is that the alphabets $\mathcal{A}$ are very
large, and so is often also the carry propagation (due to the length of the
rewriting rule). Too much redundancy may be inconvenient for other operations
– e.g. division or comparison. Therefore, our goal is to find alphabets of
minimal size allowing parallel addition. For $\beta$ being an algebraic
integer, lower bounds on the cardinality of integer alphabets $\mathcal{A}$
for parallel addition were specified in [5]; and, for several classes of the
bases $\beta$, the parallel addition algorithms using (integer) alphabets of
the minimal size were actually found ([5, 3]).

Although the alphabet $\mathcal{A}$ is most often selected as a subset of
integers, the problem is relevant also in a more general setting, namely
considering $\mathcal{A}\subset\mathbb{Z}[\beta]$. Some of the results and
conditions on the alphabet $\mathcal{A}$ to enable parallel addition, obtained
earlier for integer alphabets, were generalized in [14] also to
$\mathcal{A}\subset\mathbb{Z}[\beta]$. Especially the lower bound on minimal
cardinality of $\mathcal{A}$ in the case of
$\mathcal{A}[\beta]=\mathbb{Z}[\beta]$. It is proven that the alphabet must
contain all congruence classes modulo $\beta$ in $\mathbb{Z}[\beta]$, and also
all congruence classes modulo $\beta-1$ in $\mathbb{Z}[\beta]$. This is
already quite an important requirement to fulfil, but still leaving freedom
when selecting the digits to compose the set $\mathcal{A}$. For various
reasons, such as decreasing the computing demands for operations in
$(\beta,\mathcal{A})$, or to enable (on-line) division, we may propose the
alphabet $\mathcal{A}$ to be symmetric, or to contain the smallest possible
digits in modulus.

In the sequel, we first recall the basic terminology and known results about
parallel addition, in Section 2. Then, in Section 3, we stress the difference
between standard and parallel addition, and fix the notation to be used within
the algorithms later. Once having a hypothesis, namely a set
$\mathcal{A}\subset\mathbb{Z}[\beta]$ as the candidate for
$(\beta,\mathcal{A})$ to become a numeration system with parallel addition, we
use a so-called Extending Window Method (EWM), which tries, in an automated
and systematic way, to derive an algorithm of parallel addition for this
numeration system $(\beta,\mathcal{A})$. This idea of the EWM (a new result),
together with schemes of its main algorithms are presented in Section 4.

Usage of the Extending Window Method is limited to bases $\beta\in\mathbb{C}$
being algebraic integers, and at the same time also _expanding_ , i.e., their
conjugates must be all greater than $1$ in modulus. Convergence of the EWM is
guaranteed only for its first phase (generation of the weight coefficients
set); whereas for the second phase (assignment of the weight coefficients to
all necessary combinations of input digits), we developed tools for revealing
non-convergence. This is explained in Section 5. Nevertheless, despite these
limitations, the EWM is a valuable tool in the search for parallel addition
algorithms, because the attempts to derive the algorithms manually are very
laborious – in fact close to impossible – already for quite small alphabets
(e.g. with less than 10 digits).

Section 6 discusses generalization of EWM to bases and alphabets in
$\mathbb{Z}[\omega]$ for an algebraic integer $\omega$. It also summarizes the
basic information about the actual implementation of the EWM done in SageMath.

Although the EWM does not guarantee finding the parallel addition algorithms
in all cases where they exist, it brings a significant number of successful
results; especially when considering non-integer alphabets
$\mathcal{A}\subset\mathbb{Z}[\beta]$, and also for block parallel addition.
In Section 7, we first show that in many (but not all) cases, the EWM provides
the same parallel addition algorithms as derived earlier manually. Then, we
give examples of new results – parallel addition algorithms obtained only via
EWM.

##  2 Preliminaries and Known Results

###  2.1 Concept of Parallel Addition

The idea of parallel addition has been formalized using the notion of so-
called _$p$ -local function_:

######  Definition 2.1.

Let $\mathcal{A}$ and $\mathcal{B}$ be alphabets. A _function_
$\varphi:\mathcal{B}^{\mathbb{Z}}\rightarrow\mathcal{A}^{\mathbb{Z}}$ is said
to be _$p$ -local_ if there exist $r,t\in\mathbb{N}$ satisfying $p=r+t+1$ and
a function $\phi:\mathcal{B}^{p}\rightarrow\mathcal{A}$ such that, for any
$w=(w_{j})_{j\in\mathbb{Z}}\in\mathcal{B}^{\mathbb{Z}}$ and its image
$z=\varphi(w)=(z_{j})_{j\in\mathbb{Z}}\in\mathcal{A}^{\mathbb{Z}}$, we have
$z_{j}=\phi(w_{j+t},\dots,w_{j-r})$ for every $j\in\mathbb{Z}$. The parameters
$t$ and $r$ are called _anticipation_ and _memory_ , respectively.

This means that a window of length $p$ computes the digit $z_{j}$ of the image
$\varphi(w)$ from $(w_{j+t},\dots,w_{j-r})$, the digit $z_{j-1}$ from digits
$(w_{j+t-1},\dots,w_{j-r-1})$ etc.

Since two $(\beta,\mathcal{A})$-representations may be easily summed up digit-
wise in parallel, the crucial point of parallel addition is conversion of a
$(\beta,\mathcal{A}+\mathcal{A})$-representation of the sum to a
$(\beta,\mathcal{A})$-representation. The notion of $p$-local function is
applied to this conversion.

######  Definition 2.2.

Let $\beta$ be a base and let $\mathcal{A}$, $\mathcal{B}$ be alphabets
containing $0$. A function
$\varphi:\mathcal{B}^{\mathbb{Z}}\rightarrow\mathcal{A}^{\mathbb{Z}}$ such
that

  1. i)

for any $w=(w_{j})_{j\in\mathbb{Z}}\in\mathcal{B}^{\mathbb{Z}}$ with finitely
many non-zero digits,
$z=\varphi(w)=(z_{j})_{j\in\mathbb{Z}}\in\mathcal{A}^{\mathbb{Z}}$ has only
finite number of non-zero digits, and

  2. ii)

$\sum_{j\in\mathbb{Z}}w_{j}\beta^{j}=\sum_{j\in\mathbb{Z}}z_{j}\beta^{j}$

is called _digit set conversion_ in the base $\beta$ from $\mathcal{B}$ to
$\mathcal{A}$. Such a conversion $\varphi$ is said to be _computable in
parallel_ if $\varphi$ is a $p$-local function for some $p\in\mathbb{N}$.
_Parallel addition_ in a numeration system $(\beta,\mathcal{A})$ is a digit
set conversion in base $\beta$ from $\mathcal{A}+\mathcal{A}$ to $\mathcal{A}$
which is computable in parallel.

###  2.2 Parallel Addition Algorithms in Minimal Alphabets - Known Results

Naturally, the first class of bases where the concept of parallel addition was
introduced and studied are integers. In [1], A. Avizienis gave an algorithm
for parallel addition in numeration systems with positive integer bases
$\beta\in\mathbb{N}$, $\beta\geq 3$ and with (symmetric) integer alphabets
$\mathcal{A}=\\{-a,\ldots,0,\ldots,a\\}$, such that $\beta/2<a\leq\beta-1$.
The size of thus prescribed alphabets for parallel addition equals
$\\#\mathcal{A}=2a+1$, which is at least $\beta+2$ for $\beta$ odd and
$\beta+3$ for $\beta$ even. So the redundancy is a bit higher here (+2 and +3
digits for odd and even bases, respectively) than the minimum needed for
parallel addition (just +1 digit on top of the canonical alphabet); but, in
turn, the algorithm performing parallel addition is very simple, and the carry
propagates by just one position.

The level of redundancy in $(\beta,\mathcal{A})$ was decreased to the minimum
for even positive integer bases $\beta=2a$ (including also $\beta=2$) in the
parallel addition algorithm provided in [2]; using again symmetric alphabets,
i.e., $\mathcal{A}=\\{-a,\ldots,0,\ldots,a\\}$ with
$\\#\mathcal{A}=2a+1=\beta+1$. And in [17], B. Parhami gave the algorithms for
all positive integer bases $\beta\geq 2$, both even and odd, on any (generally
non-symmetric) alphabets of consecutive integers (containing zero) of the
minimal size $\\#\mathcal{A}=\beta+1$.

Parallel addition algorithms on (integer) alphabets of the minimal size are
provided in [5] and [3] for several classes of the bases:

  * •

positive and negative integers $\beta=\pm b$, with $b\in\mathbb{N},b\geq 2$:
on $\\#\mathcal{A}=b+1$;

  * •

positive and negative rational numbers $\beta=\pm a/b$, with
$a,b\in\mathbb{N}$ co-prime: on $\\#\mathcal{A}=a+b$;

  * •

quadratic Pisot numbers $\beta>1$ fulfilling $\beta^{2}=a\beta-b$, with
$a,b\in\mathbb{N}$, $a-2\geq b\geq 1$: on $\\#\mathcal{A}=a+b-1$;

  * •

quadratic Pisot numbers $\beta>1$ fulfilling $\beta^{2}=a\beta+b$, with
$a,b\in\mathbb{N}$, and $a-1\geq b\geq 2$ or $a\geq b=1$: on
$\\#\mathcal{A}=a+b+1$;

  * •

roots of $\beta=\sqrt[\ell]{b}$, with $\ell,b\in\mathbb{N}$, $b\geq 2$: on
$\\#\mathcal{A}=b+1$ (where $\beta$ cannot be written as
$\beta=\sqrt[\ell^{\prime\prime}]{c}$, with
$\ell=\ell^{\prime}\ell^{\prime\prime}$, $b=c^{\ell^{\prime}}$, and
$\ell^{\prime},\ell^{\prime\prime},c\in\mathbb{N}$).

As for the bases being roots of $\beta=\sqrt[\ell]{-b}$, with
$b\in\mathbb{N}$, $b\geq 2$, no general formula of parallel addition algorithm
on alphabets of minimal size has yet been provided for this class as a whole,
but just for selected individual cases (studied in [16, 5]), again on integer
alphabets:

  * •

Penney base $\beta=\imath-1$: on $\\#\mathcal{A}=5$;

  * •

Knuth base $\beta=2\imath$: on $\\#\mathcal{A}=5$;

  * •

base $\beta=\imath\sqrt{2}$: on $\\#\mathcal{A}=3$.

###  2.3 Calculating in Blocks

In [8], an alternative approach was introduced to perform calculations on
$(\beta,\mathcal{A})$-representations, namely calculating in so-called
$k$-blocks. It means that, for a given positive integer $k\geq 1$, we divide
the $(\beta,\mathcal{A})$-representation into blocks of $k$ digits, and then
treat it in fact as a $(\beta^{k},\mathcal{B})$-representation, where the
alphabet
$\mathcal{B}=\\{\sum_{j=0}^{k-1}a_{j}\beta^{j}\,|\,a_{j}\in\mathcal{A}\\}$
contains new digits with respect to new base $\beta^{k}$.

As to the problem of parallel addition, we explain in Section 2.4 that the
$k$-block concept does not broaden the set of eligible bases. Nevertheless, it
may help to decrease the size of alphabets (level of redundancy) needed for
parallel addition. This is the case e.g. of the $d$-bonacci bases – roots of
the minimal polynomials $X^{d}=X^{d-1}+X^{d-2}+\cdots+X+1$ for $d\geq 2$: here
the block concept decreases the size of the alphabet for parallel addition to
just $3$ digits, instead of the $d+1$ digits necessary for $1$-block parallel
addition.

For the so-called Canonical Number Systems (CNS, introduced by B. Kovács in
[9], and then extensively studied by others), with a complex base $\beta$ and
alphabet $\\{0,1,\ldots,|N(\beta)|-1\\}$, where $|N(\beta)|$ denotes the norm
of $\beta$ over $\mathbb{Q}$, it is proved in [3] that block parallel addition
is possible on the alphabets $\\{0,1,\ldots,2|N(\beta)|-2\\}$ or
$\\{-|N(\beta)|+1,\ldots,-1,0,1,\ldots,|N(\beta)|-1\\}$. The size of these
alphabets ($\\#\mathcal{A}=2|N(\beta)|-1$) may be substantially smaller than
the minimal size of alphabet needed for $1$-block parallel addition in the
same base $\beta$. For instance, see Section 7:

  * •

Penney base $\beta=\imath-1$ requires a $5$-digit alphabet for ($1$-block)
parallel addition, but only $3$ digits for $k$-block parallel addition: an
algorithm using $k=4$ is provided in [6], and we further diminish the block
size to $k=2$ in this work;

  * •

Eisenstein base $\beta=\exp{(2\pi\imath/3)}$ requires a $7$-digit alphabet for
($1$-block) parallel addition, but only $5$ digits for $k$-block parallel
addition: we find an algorithm using $k=3$.

###  2.4 Necessary Conditions on Bases and Alphabets for Parallel Addition

Let us recall that we still consider just finite
$(\beta,\mathcal{A})$-representations as the operands (summands to be added):

$\text{Fin}_{\mathcal{A}}(\beta)=\left\\{x=\sum_{j=R}^{L}x_{j}\beta^{j}\,|\,x_{j}\in\mathcal{A},L,R\in\mathbb{Z}\right\\}\,,$
(1)

and let us denote

$\mathcal{A}[\beta]=\left\\{\sum_{i=0}^{N}a_{i}\beta^{i}\colon
a_{i}\in\mathcal{A},\,N\in\mathbb{N}\right\\}\qquad\mathrm{and}\qquad\mathbb{Z}[\beta]=\left\\{\sum_{i=0}^{N}a_{i}\beta^{i}\colon
a_{i}\in\mathbb{Z},\,N\in\mathbb{N}\right\\}\,.$ (2)

For the case of alphabets $\mathcal{A}\subset\mathbb{Z}$ of consecutive
integers, the condition on base $\beta$ to allow parallel addition was proved
in [3], and later in [14] it was generalized to alphabets
$\mathcal{A}\subset\mathbb{Z}[\beta]$:

######  Theorem 2.3.

Let $\beta$ be a complex number such that $|\beta|>1$. There exists an
alphabet $\mathcal{A}\subset\mathbb{Z}[\beta]$ with $0\in\mathcal{A}$ and
$1\in\text{Fin}_{\mathcal{A}}(\beta)$ which allows $k$-block parallel addition
in $(\beta,\mathcal{A})$ for some $k\in\mathbb{N}$, if and only if $\beta$ is
an algebraic number with no conjugate of modulus $1$. If this is the case,
then there also exists an alphabet of consecutive integers containing $0$
which enables $1$-block parallel addition in base $\beta$.

The problem of the minimal alphabet size for parallel addition was again
studied first for the case of alphabets of consecutive integers, e.g. in [5],
and then extended in [14] to the more general case of
$\mathcal{A}\subset\mathbb{Z}[\beta]$. Those results provide not just the
lower bound on the alphabet size, but also the form of digits that have to be
contained in the alphabet, based on congruence classes modulo $\beta$ and
$\beta-1$. We recall that $\gamma,\delta\in\mathbb{Z}[\beta]$ are congruent
modulo $\alpha\in\mathbb{Z}[\beta]$ if and only if
$\gamma-\delta\in\alpha\cdot\mathbb{Z}[\beta]$.

######  Theorem 2.4.

If a numeration system $(\beta,\mathcal{A})$ with
$\mathcal{A}[\beta]=\mathbb{Z}[\beta]$ allows parallel addition, then the
alphabet $\mathcal{A}\subset\mathbb{Z}[\beta]$ contains at least one
representative of each congruence class modulo $\beta$ and modulo $\beta-1$ in
$\mathbb{Z}[\beta]$.

In the case of bases $\beta$ being algebraic integers, it is convenient that
the lower bound on the size of alphabets for parallel addition can be
expressed by means of the minimal polynomial of $\beta$:

######  Theorem 2.5.

Let $(\beta,\mathcal{A})$ be a numeration system such that
$\beta\in\mathbb{C},|\beta|>1$ is an algebraic integer with minimal polynomial
$m_{\beta}$, and let $\mathcal{A}[\beta]=\mathbb{Z}[\beta]$. If
$(\beta,\mathcal{A})$ allows parallel addition, then $\beta$ is expanding and

$\\#\mathcal{A}\geq\max\\{|m_{\beta}(0)|,|m_{\beta}(1)|\\}\,.$

Moreover, if $\beta$ has a positive real conjugate, then

$\\#\mathcal{A}\geq\max\\{|m_{\beta}(0)|,|m_{\beta}(1)|+2\\}\,.$

For completeness, let us state also the earlier result from [5], which is a
bit stronger than Theorem 2.5 for the alphabets of consecutive integers, as it
does not require that $\mathcal{A}[\beta]=\mathbb{Z}[\beta]$:

######  Theorem 2.6.

Consider a base $\beta\in\mathbb{C},|\beta|>1$, being an algebraic integer
with minimal polynomial $m_{\beta}$. Let $\mathcal{A}$ be an alphabet of
consecutive integers containing $0$ and $1$. If addition in ${\rm
Fin}_{\mathcal{A}}(\beta)$ is computable in parallel, then
$\\#\mathcal{A}\geq|m_{\beta}(1)|$. If, moreover, the base has a positive real
conjugate, then $\\#\mathcal{A}\geq|m_{\beta}(1)|+2$.

##  3 Addition – Standard vs. Parallel

The general idea of addition (standard or parallel) in any numeration system
$(\beta,\mathcal{A})$ is the following: we sum up two numbers digit-wise, and
then convert the result with digits in $\mathcal{A}+\mathcal{A}$ into the
alphabet $\mathcal{A}$. Obviously, digit-wise addition is computable in
parallel, so the problematic part is the digit set conversion of thus obtained
result. It can be easily done in a standard way (from right to left), but
parallel digit set conversion is non-trivial. Parallel conversion may be based
on the same formulas as the standard one, but the choice of so-called _weight
coefficients_ differs in general.

Let $w_{n^{\prime}}\cdots w_{1}w_{0}\bullet w_{-1}\cdots w_{-m^{\prime}}$ be a
$(\beta,\mathcal{A}+\mathcal{A})$-representation of
$w\in\text{Fin}_{\mathcal{A}+\mathcal{A}}(\beta)$ obtained by digit-wise
addition of $(\beta,\mathcal{A})$-representations of summands. We search for a
$(\beta,\mathcal{A})$-representation of $w$, i.e., a sequence $z_{n}\cdots
z_{1}z_{0}z_{-1}\cdots z_{-m}$ such that $z_{j}\in\mathcal{A}$ and
$z_{n}\cdots z_{1}z_{0}\bullet z_{-1}\cdots z_{-m}=(w)_{\beta,\mathcal{A}}$.
Note that the indices $n$ and $-m$ of the first and the last non-zero digits
of the converted representation $(w)_{\beta,\mathcal{A}}=z_{n}\cdots
z_{1}z_{0}\bullet z_{-1}\cdots z_{-m}$ generally differ from the indices
$n^{\prime}$ and $-m^{\prime}$ of the original representation
$(w)_{\beta,{\mathcal{A}+\mathcal{A}}}=w_{n^{\prime}}\cdots w_{1}w_{0}\bullet
w_{-1}\cdots w_{-m^{\prime}}$. We have $n\geq n^{\prime}$ and $m\geq
m^{\prime}$; if not, the converted representation is padded by zeros. For
easier notation, such representations can be multiplied by
$\beta^{m^{\prime}}$. Hence, without loss of generality, we can consider only
conversion of elements of $(\mathcal{A}+\mathcal{A})[\beta]$, i.e., numbers
from $\text{Fin}_{\mathcal{A}+\mathcal{A}}(\beta)$, whose representations have
all digits with negative indices equal to zero.

Digits $w_{j}$ are converted from $\mathcal{A}+\mathcal{A}$ into the alphabet
$\mathcal{A}$ by digit-wise addition of suitable representations of zero. Any
polynomial $R(x)=r_{s}x^{s}+\dots+r_{1}x+r_{0}$ with coefficients
$r_{j}\in\mathbb{Z}[\beta]$ such that $R(\beta)=0$ gives a representation of
zero in the base $\beta$. Such polynomial $R$ is called a _rewriting rule_ for
$\beta$. One of the coefficients of $R$ which is greatest in modulus (so-
called _dominant coefficient_) may be used for conversion of a digit from
$\mathcal{A}+\mathcal{A}$ into $\mathcal{A}$. Nevertheless, the Extending
Window Method proposed later in Section 4 to generate parallel addition
algorithms is strongly dependent on the rewriting rule. Therefore, usage of an
arbitrary rewriting rule $R$ is not within the scope of this work, and we
focus only on the simplest possible representation of zero – rewriting rule
deduced from the polynomial

$R(x)=x-\beta\in\left(\mathbb{Z}[\beta]\right)[x]\,.$ (3)

Since $R(\beta)=0=\beta^{j}\cdot
R(\beta)=1\cdot\beta^{j+1}-\beta\cdot\beta^{j}$ for any $j\in\mathbb{N}$,
there is a representation of zero in the form $1(-\beta)0\cdots
0\bullet=(0)_{\beta}$, with $-\beta$ on the $j$-th position. We multiply this
representation by a so-called _weight coefficient_
$q_{j}\in\mathbb{Z}[\beta]$, in order to obtain another representation of zero
in the form

$q_{j}(-q_{j}\beta)\underbrace{0\cdots 0}_{j}\bullet=(0)_{\beta}\,.$

This is digit-wise added to $w_{n}\cdots w_{1}w_{0}\bullet$ in order to
convert the digit $w_{j}$ from $\mathcal{A}+\mathcal{A}$ into the alphabet
$\mathcal{A}$. Such conversion of the $j$-th digit causes a _carry_ $q_{j}$
onto the $(j+1)$-th position, i.e., to the left neighbour. This is clear from
the column notation of digit-wise addition.

$w_{n^{\prime}}$ | $\cdots$ | $w_{j+1}$ | $w_{j}$ | $w_{j-1}$ | $\cdots$ | $w_{1}$ | $w_{0}$ | $\bullet$ | $=$ | $(w)_{\beta,{\mathcal{A}+\mathcal{A}}}$
---|---|---|---|---|---|---|---|---|---|---
|  |  | $q_{j-1}$ | $-\beta q_{j-1}$ | $\iddots$ |  |  |  | $=$ | $(0)_{\beta}$
| $\iddots$ | $q_{j}$ | $-\beta q_{j}$ |  |  |  |  |  | $=$ | $(0)_{\beta}$
$z_{n}\cdots z_{n^{\prime}}$ | $\cdots$ | $z_{j+1}$ | $z_{j}$ | $z_{j-1}$ | $\cdots$ | $z_{1}$ | $z_{0}$ | $\bullet$ | $=$ | $(w)_{\beta,{\mathcal{A}}}$

Hence, the desired formula for conversion on the $j$-th position is
$z_{j}:=w_{j}+q_{j-1}-q_{j}\beta$. The coefficient $q_{-1}$ is zero, since
there is no carry from the right onto the $0$-th position. The terms _carry_
and _weight coefficient_ are related to a specific position: a weight
coefficient $q_{j-1}$ is a carry from the right neighbour $(j-1)$ onto the
$j$-th position, $q_{j}$ is a weight coefficient chosen on the $j$-th
position, and thus $q_{j}$ is a carry from the $j$-the position onto the
$(j+1)$-th position, etc. Therefore, the conversion using the rewriting rule
$x-\beta$ prolongs the part of non-zero digits only to the left, as there is
no carry to the right. So all positions with negative indices remain with zero
digits in the converted representation $z_{n}\cdots
z_{1}z_{0}\bullet=(w)_{\beta,{\mathcal{A}}}$.

The conversion preserves the value of $w$, since only representations of zero
are added, formally

$\displaystyle\sum_{j\geq 0}z_{j}\beta^{j}$ $\displaystyle=w_{0}-\beta
q_{0}+\sum_{j>0}(w_{j}+q_{j-1}-q_{j}\beta)\beta^{j}=$
$\displaystyle=\sum_{j\geq
0}w_{j}\beta^{j}+\sum_{j>0}q_{j-1}\beta^{j}-\sum_{j\geq
0}q_{j}\cdot\beta^{j+1}=$ (4) $\displaystyle=\sum_{j\geq
0}w_{j}\beta^{j}+\sum_{j>0}q_{j-1}\beta^{j}-\sum_{j>0}q_{j-1}\cdot\beta^{j}=\sum_{j\geq
0}w_{j}\beta^{j}=w\,.$

The weight coefficients $q_{j}$ must be chosen so that the converted digits
$z_{j}$ are in the alphabet $\mathcal{A}$, namely,

$z_{j}=w_{j}+q_{j-1}-q_{j}\beta\in\mathcal{A}\mathrm{\ for\ any\
}j\in\mathbb{N}\,.$ (5)

For standard addition algorithm, the digit set conversion runs from the right
($j=0$) to the left ($j=n$), until all non-zero digits and carries are
converted into the alphabet $\mathcal{A}$. In this way, determination of the
weight coefficients is a trivial task since the carry is known when a weight
coefficient is determined.

But when designing parallel addition algorithms, choosing the weight
coefficient is the crucial and difficult task, because there might be more
possible carries from the right neighboring $(j-1)$-th position that arrive to
the $j$-th position. This is done via the Extending Window Method, as
described in Section 4. We require that the digit set conversion from
$\mathcal{A}+\mathcal{A}$ into $\mathcal{A}$ is computable in parallel, i.e.
there exist constants $r,t\in\mathbb{N}_{0}$ such that for all $j\geq 0$ it
holds that $z_{j}=z_{j}(w_{j+t},\dots,w_{j-r})$. In our case, the anticipation
$t$ equals zero, since we use the rewriting rule $x-\beta$. To avoid
dependency on all less significant digits (on the right from the processed
position), we need some variety in the choice of the weight coefficient
$q_{j}$. This implies that the used numeration system $(\beta,\mathcal{A})$
must be redundant.

The core difference between standard and parallel addition can be expressed,
for conversion of $(\beta,\mathcal{A}+\mathcal{A})$-representation
$w_{n^{\prime}}\ldots w_{1}w_{0}\bullet=(w)_{\beta,\mathcal{A}+\mathcal{A}}$
into $(\beta,\mathcal{A})$-representation $z_{n}\ldots
z_{1}z_{0}\bullet=(w)_{\beta,\mathcal{A}}$, as follows:

$\displaystyle\mathrm{standard\ addition:}\qquad z_{j}$
$\displaystyle=z_{j}(w_{j},\dots,w_{j-r},\dots,w_{0})\,,$
$\displaystyle\mathrm{parallel\ addition:}\qquad z_{j}$
$\displaystyle=z_{j}(w_{j+t},\dots,w_{j-r})\,.$

######  Remark 3.1.

Consider a base $\beta\in\mathbb{C},|\beta|>1$, and alphabet
$\mathcal{A}\subset\mathbb{Z}[\beta]$ with sets
$\mathcal{B},\mathcal{D}\subset\mathbb{Z}[\beta]$ satisfying:

$0\in\mathcal{D}\subset\mathcal{A}\subsetneq\mathcal{B}\subset\mathcal{A}+\mathcal{A}\qquad\mathrm{and}\qquad\mathcal{A}+\mathcal{D}\subset\mathcal{B}\,,$
(6)

and let $l\in\mathbb{N}$ be such that

$(\forall x\in\mathcal{A})(\exists
d^{(1)},\ldots,d^{(l)}\in\mathcal{D})(x=d^{(1)}+\cdots+d^{(l)})\,.$ (7)

Then existence of parallel conversion in base $\beta$ from $\mathcal{B}$ to
$\mathcal{A}$ implies existence of parallel conversion in base $\beta$ from
$\mathcal{A}+\mathcal{A}$ to $\mathcal{A}$, and thus also existence of
parallel addition in the numeration system $(\beta,\mathcal{A})$.
Clearly, when summing up two elements $x,y\in\text{Fin}_{\mathcal{A}}(\beta)$
expressed as $x=\sum x_{j}\beta^{j},y=\sum y_{j}\beta^{j}$ with
$x_{j},y_{j}\in\mathcal{A}$, we can use the form (7) of each
$x_{j}=d_{j}^{(1)}+\cdots+d_{j}^{(l)}$, and denote by $d^{(k)}=\sum
d_{j}^{(k)}\beta^{j}$ for each $k=1,\ldots,l$. Then, we split the operation
$x+y$ into $l$ operations, gradually producing $z^{(k)}:=d^{(k)}+z^{(k-1)}$
for $k=1,\ldots,l$, with $z^{(0)}=y$. Each $k$-th step provides a
$(\beta,\mathcal{A})$-representation of $z^{(k)}$ via parallel conversion of
$d^{(k)}+z^{(k-1)}$ from $\mathcal{A}+\mathcal{D}\subset\mathcal{B}$ to
$\mathcal{A}$. After $l$ iterations, we get the desired
$(\beta,\mathcal{A})$-representation of $z^{(l)}$ in the form

$\displaystyle z^{(l)}$
$\displaystyle=d^{(l)}+z^{(l-1)}=d^{(l)}+(d^{(l-1)}+z^{(l-2)})=\cdots$
$\displaystyle=d^{(l)}+(d^{(l-1)}+(\cdots+(d^{(1)}+y)))=\sum_{k=1}^{l}d^{(k)}+y=x+y\,.$

The number $l\in\mathbb{N}$ of iterations is fixed (not depending on
$x,y\in\text{Fin}_{\mathcal{A}}(\beta)$), and composition of a fixed number of
parallel conversions is still a parallel conversion; so we have the conversion
from $\mathcal{A}+\mathcal{A}$ to $\mathcal{A}$ done in parallel.
This approach can be easily used for alphabets $\mathcal{A}\subset\mathbb{Z}$
of consecutive integers, e.g.:

  * •

$\mathcal{A}=\\{m,\ldots,0,\ldots,M\\}$ with $\mathcal{D}=\\{0,\pm 1\\}$,
$\mathcal{B}=\\{m-1,\ldots,M+1\\}$ and $l=\max\\{-m,M\\}$; or

  * •

$\mathcal{A}=\\{0,\ldots,M\\}$ with $\mathcal{D}=\\{0,1\\}$,
$\mathcal{B}=\\{0,\ldots,M+1\\}$ and $l=M$.

In the case of complex alphabets $\mathcal{A}\subset\mathbb{Z}[\beta]$, the
application may be useful especially when bigger (non-minimal) alphabets are
considered for the parallel addition algorithm.

##  4 Extending Window Method to Construct Parallel Addition Algorithms

For a numeration system $(\beta,\mathcal{A})$ such that $\beta$ is an
algebraic integer and ${\mathcal{A}\subset\mathbb{Z}[\beta]}$, and let
$\mathcal{B}\subset\mathbb{Z}[\beta]$ be an input alphabet with
$\mathcal{A}\subsetneq\mathcal{B}\subset\mathcal{A}+\mathcal{A}$, according to
Remark 3.1. The Extending Window Method (EWM) is a newly proposed approach,
attempting to construct algorithms for digit set conversion in the base
$\beta$ from $\mathcal{B}$ to $\mathcal{A}$ computable in parallel. Due to our
choice (3) of the representation of zero used within the EWM, the resulting
parallel addition algorithms always have zero anticipation $t=0$, so carries
only from the right.

As mentioned above, the key problem is to find appropriate weight coefficients
$q_{j}\in\mathbb{Z}[\beta]$ such that

$z_{j}=\underbrace{w_{j}}_{\in\mathcal{B}}+\,q_{j-1}-q_{j}\beta\in\mathcal{A}\mathrm{\quad
for\ all\quad}j\geq 0\,,$

for any input $w\in\text{Fin}_{\mathcal{B}}(\beta)$ with
$(\beta,\mathcal{B})$-representation $w_{n^{\prime}}\dots
w_{1}w_{0}\bullet=(w)_{\beta,\mathcal{B}}$.

The digits $z_{j}$ of the result have to satisfy
$z_{j}=z_{j}(w_{j},\dots,w_{j-r})$ for some fixed memory $r\in\mathbb{N}$, so
the carries $q_{j}$ have to fulfil $q_{j}=q_{j}(w_{j},\ldots,w_{j-(r-1)})$ for
the same $r$. But the fact that the converted digit is on the $j$-th position
is not important – the conversion must proceed in the same way on every
position. Therefore, we simplify the notation by omitting the index $j$ from
the subscripts. From now on, $w_{0}\in\mathcal{B}$ is the converted digit,
$w_{-1}w_{-2}\dots\in\mathcal{B}$ are its neighboring digits on the right,
$q_{-1}\in\mathbb{Z}[\beta]$ is the carry from the right, and we search for a
weight coefficient $q_{0}\in\mathbb{Z}[\beta]$ such that

$z_{0}=w_{0}+q_{-1}-q_{0}\beta\in\mathcal{A}\,.$

Before describing the Extending Window Method, let us introduce two
definitions:

######  Definition 4.1.

Let $(\beta,\mathcal{A})$ be a numeration system, and let
$\mathcal{B}\subset\mathbb{Z}[\beta]$ be a digit set such that
$\mathcal{A}\subsetneq\mathcal{B}\subset\mathcal{A}+\mathcal{A}$. Any finite
set $\mathcal{Q}\subset\mathbb{Z}[\beta]$ containing $0$ such that

$\mathcal{B}+\mathcal{Q}\subset\mathcal{A}+\beta\mathcal{Q}$

is called a _weight coefficients set_ for the given numeration system
$(\beta,\mathcal{A})$ and input digit set $\mathcal{B}$.

A weight coefficients set $\mathcal{Q}\subset\mathbb{Z}[\beta]$ satisfies

$(\forall w_{0}\in\mathcal{B})(\forall q_{-1}\in\mathcal{Q})(\exists
q_{0}\in\mathcal{Q})(\underbrace{w_{0}+q_{-1}-q_{0}\beta}_{z_{0}}\in\mathcal{A})\,.$
(8)

In other words, there is a weight coefficient $q_{0}\in\mathcal{Q}$ for any
carry $q_{-1}\in\mathcal{Q}$ from the right and for any digit $w_{0}$ from the
input alphabet $\mathcal{B}$, such that $z_{0}=w_{0}+q_{-1}-q_{0}\beta$ is in
the target alphabet $\mathcal{A}$.

######  Definition 4.2.

Let $\mathcal{Q}\subset\mathbb{Z}[\beta]$ be a weight coefficients set for
numeration system $(\beta,\mathcal{A})$ and input digit set
$\mathcal{B}\subset\mathbb{Z}[\beta]$. Let $r\in\mathbb{N}$, and let
$q:\mathcal{B}^{r}\rightarrow\mathcal{Q}$ be a mapping such that

$\displaystyle w_{0}+q(w_{-1},\dots,w_{-r})-\beta q(w_{0},\dots,w_{-(r-1)})$
$\displaystyle\in\mathcal{A}\text{ for\ any
}w_{0},w_{-1},\dots,w_{-r}\in\mathcal{B}\,,$ $\displaystyle\text{and}\quad
q(0,\dots,0)$ $\displaystyle=0\,.$

Such mapping $q$ is called _weight function of length_ $r$ for
$(\beta,\mathcal{A})$ and input digit set $\mathcal{B}$.

Having a weight function $q:\mathcal{B}^{r}\rightarrow\mathcal{Q}$, we define
a function $\phi:\mathcal{B}^{r+1}\rightarrow\mathcal{A}$ by the formula

$\phi(w_{0},\dots,w_{-r})=w_{0}+\underbrace{q(w_{-1},\dots,w_{-r})}_{=q_{-1}}-\beta\underbrace{q(w_{0},\dots,w_{-(r-1)})}_{=q_{0}}=:z_{0}\in\mathcal{A}\,,$
(9)

and thus obtain the digit set conversion from $\mathcal{B}$ to $\mathcal{A}$
in base $\beta$ as $(r+1)$-local function, with anticipation $0$ and memory
$r$. The requirement that $q(0,\ldots,0)=0$, i.e., zero output of the weight
function $q$ for the input of $r$ zeros, guarantees that $\phi(0,\dots,0)=0$.
Thus, the first condition of Definition 2.2 is satisfied. The second condition
follows from the equation (3).

Let us recall the principle of the digit set conversion algorithms based on
the rewriting rule $x-\beta$. Assume existence of the weight coefficients set
$\mathcal{Q}$ and the weight function
$q:\mathcal{B}^{r}\rightarrow\mathcal{Q}$ for the given numeration system
$(\beta,\mathcal{A})$ and the input digit set $\mathcal{B}$. To convert
$w_{n^{\prime}}\ldots w_{1}w_{0}\bullet=(w)_{\beta,\mathcal{B}}$ into
$z_{n}\ldots z_{1}z_{0}\bullet=(w)_{\beta,\mathcal{A}}$, first assign the
weight coefficients $q\in\mathcal{Q}$ for each position – independently, so
all at once (in parallel). Then multiply the rewriting rule by the weight
coefficients $q$, and add them digit-wise to the input sequence. In fact, it
means that the equation (5) is applied on each position independently. The
digit set conversion is computable in parallel thanks to the fact that the
weight coefficients are determined as outputs of the weight function $q$ of a
fixed length $r$.

In order to enable this way of computation, we introduce the so-called
_Extending Window Method_. It works in two phases, for a given numeration
system $(\beta,\mathcal{A})$ and an input digit set $\mathcal{B}$. First, it
finds some weight coefficients set $\mathcal{Q}\subset\mathbb{Z}[\beta]$, as
described in Definition 4.1. This set $\mathcal{Q}$ then serves as the
starting point for the second phase, in which we gradually increment the
expected length $r$, until the weight function
$q:\mathcal{B}^{r}\rightarrow\mathcal{Q}$ is uniquely defined for each
$(w_{0},\dots,w_{-(r-1)})\in\mathcal{B}^{r}$, as required in Definition 4.2.
If both these phases are successful, the local conversion function is finally
determined – we use the weight function outputs $q$ as the weight coefficients
in the formula (9).

Further in this section, we describe construction of the weight coefficients
sets and the weight functions, in the two phases respectively. Convergence of
both phases is then discussed in Section 5.

###  4.1 Phase 1 – Weight Coefficients Set

The goal of the first phase is to compute a weight coefficients set
$\mathcal{Q}\subset\mathbb{Z}[\beta]$, i.e., find a set $\mathcal{Q}\ni 0$
such that

$\mathcal{B}+\mathcal{Q}\subset\mathcal{A}+\beta\mathcal{Q}\,.$

We build a sequence $\mathcal{Q}_{0},\mathcal{Q}_{1},\mathcal{Q}_{2},\dots$ of
sets $\mathcal{Q}_{k}\subset\mathbb{Z}[\beta]$ iteratively, by extending
$\mathcal{Q}_{k}$ to $\mathcal{Q}_{k+1}$ in such a way that all elements of
the set $\mathcal{B}+\mathcal{Q}_{k}$ get covered by elements of the extended
set $\mathcal{Q}_{k+1}$:

$\mathcal{B}+\mathcal{Q}_{k}\subset\mathcal{A}+\beta\mathcal{Q}_{k+1}\,.$

This procedure is repeated until the extended weight coefficients set
$\mathcal{Q}_{k+1}$ is the same as the previous set $\mathcal{Q}_{k}$. In the
sequel, we use the expression _weight coefficient $q$ covers an element $x$_,
meaning that there is a digit $a\in\mathcal{A}$ such that $x=a+\beta q$.

We start with $\mathcal{Q}_{0}=\\{0\\}$, search for all weight coefficients
$q_{0}$ necessary to cover all elements $x\in\mathcal{B}$, and add them to the
set $\mathcal{Q}_{0}$ to obtain the set $\mathcal{Q}_{1}$. Then, assume that
we have the set $\mathcal{Q}_{k}$ for some $k\geq 1$. The weight coefficients
in $\mathcal{Q}_{k}$ now may appear as the carries $q_{-1}$. If there are no
suitable coefficients $q_{0}$ in the set $\mathcal{Q}_{k}$ to cover all sums
$x=b+q_{-1}$ of coefficients $q_{-1}\in\mathcal{Q}_{k}$ and digits
$b\in\mathcal{B}$, we extend $\mathcal{Q}_{k}$ to $\mathcal{Q}_{k+1}$ with
such suitable coefficients, and increase $k:=k+1$. And so on, until there is
no need to add more elements into $\mathcal{Q}_{k}$, as the set
$\mathcal{Q}_{k}$ already covers all elements from
$\mathcal{B}+\mathcal{Q}_{k}$, so in fact $Q_{k}=Q_{k+1}$. Then the weight
coefficients set $\mathcal{Q}:=\mathcal{Q}_{k}=Q_{k+1}$ satisfies the
Definition 4.1. Algorithmic description of this process in quasi-code is
summarized in Algorithm 1. Section 5.1 discusses the convergence of Phase 1,
namely the conditions under which it actually happens that
$\mathcal{Q}_{k+1}=\mathcal{Q}_{k}$ for some $k\in\mathbb{N}$.

Algorithm 1 Search for weight coefficients set $\mathcal{Q}$ (Phase 1)

0: numeration system $(\beta,\mathcal{A})$, input digit set $\mathcal{B}$

1: $k:=-1$

2: $Q_{0}:=\\{0\\}$

3: repeat

4: $k:=k+1$

5: set $C_{x}:=\\{\frac{x-a}{\beta}\colon a\in\mathcal{A},x-a\text{ is
divisible by }\beta\\}$ for each $x\in\mathcal{B}+\mathcal{Q}_{k}$

6: extend $\mathcal{Q}_{k}$ to $\mathcal{Q}_{k+1}$ so that
$\mathcal{B}+\mathcal{Q}_{k}\subset\mathcal{A}+\beta\mathcal{Q}_{k+1}$, i.e.,
$C_{x}\cap\mathcal{Q}_{k+1}\neq\emptyset$ for each
$x\in\mathcal{B}+\mathcal{Q}_{k}$ (e.g. by Algorithm 2)

7: until $\mathcal{Q}_{k}=\mathcal{Q}_{k+1}$

8: $\mathcal{Q}:=\mathcal{Q}_{k}$

8: weight coefficients set $\mathcal{Q}$

Note that the extension of $\mathcal{Q}_{k}$ to $\mathcal{Q}_{k+1}$ is not
unique. Algorithm 2 shows two possible ways of such construction. Let
$C_{x}=\\{\frac{x-a}{\beta}\colon a\in\mathcal{A},x-a\text{ is divisible by
}\beta\\}$ for each $x\in\mathcal{B}+\mathcal{Q}_{k}$, and let
$\mathcal{Q}^{\prime}_{k+1}$ contain all elements of $\mathcal{Q}_{k}$ and
elements from all $C_{x}$ such that $\\#C_{x}=1$. The set
$\mathcal{Q}^{\prime}_{k+1}$ is then extended to $\mathcal{Q}_{k+1}$ by adding
all smallest elements from every $C_{x}$ such that
$C_{x}\cap\mathcal{Q}^{\prime}_{k+1}=\emptyset$. Different norms may be used
to determine the smallest elements, e.g. the absolute value or the
$\beta$-norm from Definition 5.5. Other methods of extending $\mathcal{Q}_{k}$
to $\mathcal{Q}_{k+1}$ are suggested in [12].

Algorithm 2 Extending intermediate weight coefficients set $Q_{k}\rightarrow
Q_{k+1}$ (Phase 1)

0: previous interim weight coefficients set $\mathcal{Q}_{k}$, list of
candidates $C_{x}$ for each $x\in\mathcal{B}+\mathcal{Q}_{k}$

1:
$\mathcal{Q}_{k+1}:=\mathcal{Q}_{k}\cup\\{q\colon\\#C_{x}=1,C_{x}=\\{q\\},x\in\mathcal{B}+\mathcal{Q}_{k}\\}$

2: for all $x\in\mathcal{B}+\mathcal{Q}_{k}$ do

3: if $C_{x}\cap\mathcal{Q}_{k+1}=\emptyset$ then

4: add all smallest elements in absolute value (or, alternatively, in
$\beta$-norm) of $C_{x}$ to $\mathcal{Q}_{k+1}$

5: end if

6: end for

6: intermediate weight coefficients set $\mathcal{Q}_{k+1}$

###  4.2 Phase 2 – Weight Function

In the second phase, we want to find a length $r\in\mathbb{N}$ and a weight
function $q:\mathcal{B}^{r}\rightarrow\mathcal{Q}$. We start with the weight
coefficients set $\mathcal{Q}$ obtained in Phase 1. The idea is to reduce the
number of necessary weight coefficients which are used to convert a given
input digit up to just one single value. This is done by increasing gradually
the number $r$ of considered input digits (to the right). When we know more
digits (right neighbours of the processed input digit) that cause the carry
from the right, then we may be able to decrease the set of possible carries
from the right, and consequently need less weight coefficients to convert the
input digit into $\mathcal{A}$.

We introduce a notation for the sets of possible weight coefficients for given
input digits. If $w_{0}\in\mathcal{B}$, then $\mathcal{Q}_{[w_{0}]}$ denotes a
subset of $\mathcal{Q}$ such that

$(\forall q_{-1}\in\mathcal{Q})(\exists
q_{0}\in\mathcal{Q}_{[w_{0}]})(w_{0}+q_{-1}-q_{0}\beta\in\mathcal{A})\,.$

It means that, since the input digits on the right side from the processed
input digit can be arbitrary, any carry $q_{-1}$ from the set $\mathcal{Q}$ is
possible. However, we may be able to limit the set $\mathcal{Q}$ to its subset
$\mathcal{Q}_{[w_{0}]}$ of weight coefficients which allow the conversion of
$w_{0}$ to $\mathcal{A}$, due to knowledge of the input digit $w_{0}$ itself.

By induction with respect to $k\in\mathbb{N},k\geq 1$, for all
$(w_{0},\dots,w_{-k})\in\mathcal{B}^{k+1}$, let
$\mathcal{Q}_{[w_{0},\dots,w_{-k}]}$ denote a subset of
$\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}$ such that

$(\forall q_{-1}\in\mathcal{Q}_{[w_{-1},\dots,w_{-k}]})(\exists
q_{0}\in\mathcal{Q}_{[w_{0},\dots,w_{-k}]})(w_{0}+q_{-1}-q_{0}\beta\in\mathcal{A})\,.$

The sets $\mathcal{Q}_{[w_{0},\dots,w_{-k}]}$ of possible weight coefficients,
and consequently a weight function $q$, are constructed by Algorithm 3. The
idea is to check all possible right carries $q_{-1}\in\mathcal{Q}$ and
determine a minimal subset of values $q_{0}\in\mathcal{Q}$ such that

$z_{0}=w_{0}+q_{-1}-q_{0}\beta\in\mathcal{A}\,.$

So we obtain a subset $\mathcal{Q}_{[w_{0}]}\subset\mathcal{Q}$ of weight
coefficients which are necessary to cover the sum of the digit $w_{0}$ with
any carry $q_{-1}\in\mathcal{Q}$. This is done separately for every
$w_{0}\in\mathcal{B}$, so that we obtain such a subset
$\mathcal{Q}_{[w_{0}]}\subset\mathcal{Q}$ for all $w_{0}\in\mathcal{B}$. Then,
assuming that we know the input digit $w_{-1}$, the set of possible carries
from the right is also reduced to $\mathcal{Q}_{[w_{-1}]}$. Thus we may
consider the pair $(w_{0},w_{-1})$ of input digits, and reduce the set
$\mathcal{Q}_{[w_{0}]}$ to a set
$\mathcal{Q}_{[w_{0},w_{-1}]}\subset\mathcal{Q}_{[w_{0}]}$, which is again a
minimal subset necessary to cover all elements of
$w_{0}+\mathcal{Q}_{[w_{-1}]}$.

In the $k$-th step, we search for a minimal subset
$\mathcal{Q}_{[w_{0},\dots,w_{-k}]}\subset\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}$
such that

$w_{0}+\mathcal{Q}_{[w_{-1},\dots,w_{-k}]}\subset\mathcal{A}+\beta\mathcal{Q}_{[w_{0},\dots,w_{-k}]}\,.$

Apart from the processed digit itself, we consider here also $k$ digits on the
right. To construct the set $\mathcal{Q}_{[w_{0},\dots,w_{-k}]}$, we select
from $\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}$ such weight coefficients which
are necessary to cover the sums of digits $w_{0}+q_{-1}$, with all possible
carries $q_{-1}$ from the set $\mathcal{Q}_{[w_{-1},\dots,w_{-k}]}$.

Proceeding in this manner may lead to a unique weight coefficient $q_{0}$ for
long enough $r$-tuple of considered input digits $(w_{0},\ldots,w_{-(r-1)})$.
If there is $r\in\mathbb{N}$ such that

$\\#\mathcal{Q}_{[w_{0},\dots,w_{-(r-1)}]}=1\mathrm{\quad for\
all\quad}(w_{0},\dots,w_{-(r-1)})\in\mathcal{B}^{r}\,,$

then the output $q(w_{0},\dots,w_{-(r-1)})$ is defined as the only element of
$\mathcal{Q}_{[w_{0},\dots,w_{-(r-1)}]}$. To verify that

$z_{0}=\phi(w_{0},\dots,w_{-r})=w_{0}+\underbrace{q(w_{-1},\dots,w_{-r})}_{=q_{-1}}-\beta\underbrace{q(w_{0},\dots,w_{-(r-1)})}_{=q_{0}}$

is an element of the alphabet $\mathcal{A}$, just recall that
$q_{0}=q(w_{0},\dots,w_{-(r-1)})$ is the only element of the set
$\mathcal{Q}_{[w_{0},\dots,w_{-(r-1)}]}$, which was constructed so that

$w_{0}+\mathcal{Q}_{[w_{-1},\dots,w_{-(r-1)}]}\subset\mathcal{A}+\beta\mathcal{Q}_{[w_{0},\dots,w_{-(r-1)}]}\,.$

At the same time, $q_{-1}=q(w_{0},\dots,w_{-(r-1)})$ is the only element of
$\mathcal{Q}_{[w_{-1},\dots,w_{-r}]}$, which is a subset of
$\mathcal{Q}_{[w_{-1},\dots,w_{-(r-1)}]}$.

Unfortunately, finiteness of Phase 2 is not guaranteed. Some ways that might
reveal non-convergence are discussed in Section 5.2.

Algorithm 3 Search for weight function $q$ (Phase 2)

0: numeration system $(\beta,\mathcal{A})$, input digit set $\mathcal{B}$,
weight coefficients set $\mathcal{Q}$

1: for all $w_{0}\in\mathcal{B}$ do

2: find set $\mathcal{Q}_{[w_{0}]}\subset\mathcal{Q}$ such that
$w_{0}+\mathcal{Q}\subset\mathcal{A}+\beta\mathcal{Q}_{[w_{0}]}$ (e.g. by
Algorithm 4)

3: end for

4: $k:=0$

5: while
$\max\\{\\#\mathcal{Q}_{[w_{0},\dots,w_{-k}]}\colon(w_{0},\dots,w_{-k})\in\mathcal{B}^{k+1}\\}>1$
do

6: $k:=k+1$

7: for all $(w_{0},\dots,w_{-k})\in\mathcal{B}^{k+1}$ do

8: find set
$\mathcal{Q}_{[w_{0},\dots,w_{-k}]}\subset\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}$
such that
$w_{0}+\mathcal{Q}_{[w_{-1},\dots,w_{-k}]}\subset\mathcal{A}+\beta\mathcal{Q}_{[w_{0},\dots,w_{-k}]}$(e.g.
by Algorithm 4)

9: end for

10: end while

11: $r:=k+1$

12: $q(w_{0},\dots,w_{-(r-1)}):=$ the only element of
$\mathcal{Q}_{[w_{0},\dots,w_{-(r-1)}]}$, for each
$(w_{0},\dots,w_{-(r-1)})\in\mathcal{B}^{r}$

12: weight function $q:\mathcal{B}^{r}\rightarrow\mathcal{Q}$

Similarly to Phase 1, the choice of $\mathcal{Q}_{[w_{0},\dots,w_{-k}]}$ is
not unique. A list of different methods of choice is in [12], the Algorithm 4
below describes just two of them. Given a $(k+1)$-tuple of input digits
$(w_{0},\ldots,w_{-k})\in\mathcal{B}^{k+1}$, the set of possible carries
$\mathcal{Q}_{[w_{-1},\dots,w_{-k}]}$ from the right to $w_{0}$, and the
previous set of possible weight coefficients
$\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}$ for $w_{0}$, let
$D_{x}=\\{q_{0}\in\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}\colon\,\exists\,a\in\mathcal{A}:x=a+\beta
q_{0}\\}$ for each $x\in w_{0}+\mathcal{Q}_{[w_{-1},\dots,w_{-k}]}$. First, we
put into $\mathcal{Q}_{[w_{0},\dots,w_{-k}]}$ the elements of all $D_{x}$ such
that $\\#D_{x}=1$. Then, we repeat the following procedure while the set
$D=\\{D_{x}\colon x\in
w_{0}+\mathcal{Q}_{[w_{-1},\dots,w_{-k}]},D_{x}\cap\mathcal{Q}_{[w_{0},\dots,w_{-k}]}=\emptyset\\}$
is non-empty. Let $D^{\prime}$ be all sets in $D$ of the minimal size, and let
$g$ be the center of gravity of $\mathcal{Q}_{[w_{0},\dots,w_{-k}]}$
considered as complex numbers. Let $T$ be all elements of $\bigcup D^{\prime}$
closest to $g$ in absolute value, or alternatively, the smallest in
$\beta$-norm (see Definition 5.5). We add a deterministically chosen element
of $T$ to $\mathcal{Q}_{[w_{0},\dots,w_{-k}]}$, update $D$, and continue the
while loop. When the loop ends, i.e., every $D_{x}$ has non-empty intersection
with $\mathcal{Q}_{[w_{0},\dots,w_{-k}]}$, we have the desired result.

Algorithm 4 Search for set
$\mathcal{Q}_{[w_{0},\dots,w_{-k}]}\subset\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}$
(Phase 2)

0: input digits $(w_{0},\ldots,w_{-k})\in\mathcal{B}^{k+1}$, set of possible
carries $\mathcal{Q}_{[w_{-1},\dots,w_{-k}]}$, previous set of possible weight
coefficients $\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}$

1:
$D_{x}:=\\{q_{0}\in\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}\colon\,\exists\,a\in\mathcal{A}:x=a+\beta
q_{0}\\}$ for each $x\in w_{0}+\mathcal{Q}_{[w_{-1},\dots,w_{-k}]}$

2: $D:=\\{D_{x}\colon x\in w_{0}+\mathcal{Q}_{[w_{-1},\dots,w_{-k}]}\\}$

3: $\mathcal{Q}_{[w_{0},\dots,w_{-k}]}:=\\{q\colon\\{q\\}\in D\\}$

4: $D:=\\{D_{x}\in D\colon
D_{x}\cap\mathcal{Q}_{[w_{0},\dots,w_{-k}]}=\emptyset\\}$

5: while $D\neq\emptyset$ do

6: $m:=\min\\{\\#D_{x}\colon D_{x}\in D\\}$

7: $D^{\prime}:=\\{D_{x}\in D\colon\\#D_{x}=m\\}$

8: $g:=$ center of gravity of elements of $\mathcal{Q}_{[w_{0},\dots,w_{-k}]}$
as complex numbers

9: $T:=$ elements of $\bigcup D^{\prime}$ which are closest to $g$ in absolute
value (alternatively, $T:=$ elements of $\bigcup D^{\prime}$ which are
smallest in $\beta$-norm)

10: $q:=$ deterministically chosen element of $T$ (e.g. the lexicographically
smallest one)

11:
$\mathcal{Q}_{[w_{0},\dots,w_{-k}]}:=\mathcal{Q}_{[w_{0},\dots,w_{-k}]}\cup\\{q\\}$

12: $D:=\\{D_{x}\in D\colon
D_{x}\cap\mathcal{Q}_{[w_{0},\dots,w_{-k}]}=\emptyset\\}$

13: end while

13: $\mathcal{Q}_{[w_{0},\dots,w_{-k}]}$

Notice that, for a given length $r\in\mathbb{N}$, the number of calls of
Algorithm 4 within Algorithm 3 is

$\sum_{k=0}^{r-1}\\#\mathcal{B}^{k+1}=\\#\mathcal{B}\frac{\\#\mathcal{B}^{r}-1}{\\#\mathcal{B}-1}\,.$

It implies that the time complexity grows exponentially. The required memory
is also exponential, as we have to store the sets
$\mathcal{Q}_{[w_{0},\dots,w_{-k}]}$ for all
$(w_{0},\dots,w_{-k})\in\mathcal{B}^{k+1}$, at least for $k=r-1$.

##  5 Convergence of Extending Window Method

###  5.1 Convergence of Phase 1

In this section, we show that, if the Extending Window Method converges, then
the base $\beta\in\mathbb{C}$ must be _expanding_ , i.e., all its conjugates
are greater than $1$ in modulus. Then we prove that this property – expanding
base – is also a sufficient condition for convergence of Phase 1, provided
that the alphabet $\mathcal{A}\subset\mathbb{Z}[\beta]$ contains at least one
representative of each congruence class modulo $\beta$ in $\mathbb{Z}[\beta]$.
We see from Theorem 2.4 that the requirements put on the alphabet
$\mathcal{A}$ are in line with the necessary conditions on
$(\beta,\mathcal{A})$ for parallel addition.

######  Theorem 5.1.

Let $\mathcal{A}\subset\mathbb{Z}[\beta]$ be an alphabet such that
$1\in\mathcal{A}[\beta]$. If the Extending Window Method with the rewriting
rule $x-\beta$ converges for numeration system $(\beta,\mathcal{A})$, then the
base $\beta$ is expanding.

###### Proof.

By Corollary 3.6 in [14], if the numeration system $(\beta,\mathcal{A})$
allows parallel addition without anticipation (i.e., $t=0$ in Definition 2.1),
then $\beta$ is expanding. Parallel addition produced by the EWM is indeed
without anticipation, since there is no carry to the right when using the
rewriting rule $x-\beta$. ∎

We need to define a norm in $\mathbb{Z}[\beta]$, in order to prove Lemma 5.6,
which provides a finite set of weight coefficients $\mathcal{Q}$. Finiteness
of $\mathcal{Q}$ is crucial for the proof of convergence of Phase 1. We
exploit the fact that
$\mathbb{Z}[\beta]=\\{\sum_{i=0}^{d-1}u_{i}\beta^{i}\colon
u_{i}\in\mathbb{Z}\\}$, where $d$ is the degree of $\beta$, if and only if
$\beta$ is an algebraic integer. Hence, there is an obvious bijection
$\pi:\mathbb{Z}[\beta]\rightarrow\mathbb{Z}^{d}$ given by

$\pi(u)=({u}_{0},{u}_{1},\cdots,{u}_{d-1})^{T}\quad\text{ for every
}u=\sum_{i=0}^{d-1}u_{i}\beta^{i}\in\mathbb{Z}[\beta]\,.$

Using the concept of companion matrix, the additive group $\mathbb{Z}^{d}$ can
be equipped with multiplication such that the mapping $\pi$ is a ring
isomorphism (e.g. see [11]). For our purpose, the following lemma is
sufficient.

######  Lemma 5.2.

Let $\beta\in\mathbb{C}$ be an algebraic integer with the minimal polynomial
$m_{\beta}(x)=x^{d}+p_{d-1}x^{d-1}+\cdots+p_{1}x+p_{0}\in\mathbb{Z}[x]$. If
$S_{\beta}$ is the companion matrix of $m_{\beta}$, i.e.,

$S_{\beta}=\begin{pmatrix}0&0&\cdots&0&-p_{0}\\\ 1&0&\cdots&0&-p_{1}\\\
0&1&\cdots&0&-p_{2}\\\ \vdots&&\ddots&&\vdots\\\
0&0&\cdots&1&-p_{d-1}\end{pmatrix}\in\mathbb{Z}^{d\times d}\,,$

then $\pi(\beta u)=S_{\beta}\cdot\pi(u)$ for any
$u=\sum_{i=0}^{d-1}u_{i}\beta^{i}\in\mathbb{Z}[\beta]$.

###### Proof.

If $\pi(u)=({u}_{0},{u}_{1},\cdots,{u}_{d-1})^{T}$, then

$\displaystyle\pi(\beta u)$
$\displaystyle=\pi\left(\beta\sum_{i=0}^{d-1}u_{i}\beta^{i}\right)=\pi\left(u_{d-1}\underbrace{(-p_{d-1}\beta^{d-1}-\dots-
p_{1}\beta-p_{0})}_{=\beta^{d}}+\sum_{i=0}^{d-2}u_{i}\beta^{i+1}\right)$
$\displaystyle=\pi\left(-p_{0}u_{d-1}+\sum_{i=1}^{d-1}(u_{i-1}-u_{d-1}p_{i})\beta^{i}\right)$
$\displaystyle=(-p_{0}u_{d-1},u_{0}-u_{d-1}p_{1},\dots,u_{d-2}-u_{d-1}p_{d-1})=S_{\beta}\cdot\pi(u)\,.$

∎

We define a vector norm and a matrix norm induced by a given diagonalizable
matrix, and the following Lemma 5.4 shows selected properties of the norm
given by the companion matrix $S_{\beta}$ and $S_{\beta}^{-1}$.

######  Definition 5.3.

Let $M\in\mathbb{C}^{n\times n}$ be a diagonalizable matrix, and let
$P\in\mathbb{C}^{n\times n}$ be a nonsingular matrix which diagonalizes $M$,
i.e., $M=P^{-1}DP$ for some diagonal matrix $D\in\mathbb{C}^{n\times n}$. We
define a  _vector norm_ $\left\lVert\cdot\right\rVert_{M}$ by

$\left\lVert x\right\rVert_{M}:=\left\lVert
Px\right\rVert_{2}\quad\mathrm{for\ all}\ x\in\mathbb{C}^{n}\,,$

where $\left\lVert\cdot\right\rVert_{2}$ is the Euclidean norm. A  _matrix
norm_
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{M}$
is induced by the vector norm $\left\lVert\cdot\right\rVert_{M}$ by

${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|A\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{M}:=\sup_{\left\lVert
x\right\rVert_{M}=1}\left\lVert Ax\right\rVert_{M}\quad\mathrm{for\ all}\
A\in\mathbb{C}^{n\times n}\,.$

######  Lemma 5.4.

Let $\beta$ be an algebraic integer of degree $d$. If $S_{\beta}$ is the
companion matrix of the minimal monic polynomial $m_{\beta}$ of $\beta$, then

$\displaystyle{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|S_{\beta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{S_{\beta}}$
$\displaystyle=\max\\{|\beta^{\prime}|\colon\beta^{\prime}\text{ is conjugate
of }\beta\\},\text{ and }$
$\displaystyle{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|S_{\beta}^{-1}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{S_{\beta}}$
$\displaystyle=\max\left\\{\frac{1}{|\beta^{\prime}|}\colon\beta^{\prime}\text{
is a conjugate of }\beta\right\\}\,.$

###### Proof.

It is well known that the characteristic polynomial of the companion matrix
$S_{\beta}$ is $m_{\beta}$ (see e.g. [7]). Since the minimal polynomial
$m_{\beta}$ has no multiple roots, $S_{\beta}$ is diagonalizable over
$\mathbb{C}$. Namely, there is a nonsingular complex matrix $P$ such that
$S_{\beta}=P^{-1}DP$, where $D$ is diagonal matrix with the conjugates of
$\beta$ on the diagonal. Therefore, the norms
$\left\lVert\cdot\right\rVert_{S_{\beta}}$ and
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{S_{\beta}}$
are well-defined. Since the matrix $S_{\beta}^{-1}$ is also diagonalized by
$P$, the vector norms $\left\lVert\cdot\right\rVert_{S_{\beta}}$ and
$\left\lVert\cdot\right\rVert_{S_{\beta}^{-1}}$ are the same, and so are the
induced matrix norms
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{S_{\beta}}$
and
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{S_{\beta}^{-1}}$.

Now, we use a known result from matrix theory [7]: if $M\in\mathbb{C}^{n\times
n}$ is a diagonalizable matrix, then the spectral radius $\rho(M)$ of the
matrix $M$ equals
$\rho(M)={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|M\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{M}$.
Since the eigenvalues of $S_{\beta}$ are the conjugates of $\beta$, we have

${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|S_{\beta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{S_{\beta}}=\rho(S_{\beta})=\max\\{|\beta^{\prime}|\colon\beta^{\prime}\text{
is conjugate of }\beta\\}\,.$

Similarly,

${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|S_{\beta}^{-1}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{S_{\beta}}={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|S_{\beta}^{-1}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{S_{\beta}^{-1}}=\rho(S_{\beta}^{-1})=\max\\{\frac{1}{|\beta^{\prime}|}\colon\beta^{\prime}\text{
is conjugate of }\beta\\}\,,$

where we use the fact that the eigenvalues of $S_{\beta}^{-1}$ are reciprocal
of the eigenvalues of $S_{\beta}$. ∎

Finally, we may define a norm in $\mathbb{Z}[\beta]$.

######  Definition 5.5.

Let $\pi$ be the isomorphism between $\mathbb{Z}[\beta]$ and
$(\mathbb{Z}^{d},+,\odot_{\beta})$. Using notation from the previous Lemma
5.4, we define _$\beta$ -norm_
$\left\lVert\cdot\right\rVert_{\beta}:\mathbb{Z}[\beta]\rightarrow\mathbb{R}^{+}_{0}$
by

$\left\lVert
x\right\rVert_{\beta}=\left\lVert\pi(x)\right\rVert_{S_{\beta}}\quad\mathrm{for\
all}\ x\in\mathbb{Z}[\beta]\,.$

An important property of the $\beta$-norm is that, for a given constant $K>0$,
there are only finitely many elements of $\mathbb{Z}[\beta]$ bounded by $K$ in
this norm. The explanation is as follows: images of elements of
$\mathbb{Z}[\beta]$ under the isomorphism $\pi$ are integer vectors, and there
are only finitely many integer vectors in any finite-dimensional vector space
bounded by any norm. It is a consequence of equivalence of all norms on a
finite-dimensional vector space.

######  Lemma 5.6.

Let $\beta\in\mathbb{C}$ be an expanding algebraic integer of degree $d$. If
$\mathcal{A}$ and $\mathcal{B}$ are finite subsets of $\mathbb{Z}[\beta]$ such
that $\mathcal{A}$ contains at least one representative of each congruence
class modulo $\beta$ in $\mathbb{Z}[\beta]$, then there exists a finite set
$\mathcal{Q}\subset\mathbb{Z}[\beta]$ such that
$\mathcal{B}+\mathcal{Q}\subset\mathcal{A}+\beta\mathcal{Q}$.

###### Proof.

We use the mapping $\pi:\mathbb{Z}[\beta]\rightarrow\mathbb{Z}^{d}$ and the
$\beta$-norm $\left\lVert\cdot\right\rVert_{\beta}$ to give a bound on
elements of $\mathbb{Z}[\beta]$. Let $\gamma$ be the smallest conjugate of
$\beta$ in modulus. Denote $C:=\max\\{\left\lVert
b-a\right\rVert_{\beta}\colon a\in\mathcal{A},b\in\mathcal{B}\\}$.
Consequently, set

$R:=\frac{C}{|\gamma|-1}\mathrm{\quad
and\quad}\mathcal{Q}:=\\{q\in\mathbb{Z}[\beta]\colon\left\lVert
q\right\rVert_{\beta}\leq R\\}\,.$ (10)

By Lemma 5.4, we have

${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|S_{\beta}^{-1}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{S_{\beta}}=\max\left\\{\frac{1}{|\beta^{\prime}|}\colon\beta^{\prime}\text{
is conjugate of }\beta\right\\}=\frac{1}{|\gamma|}\,.$

Also, we have $|\gamma|>1$, as $\beta$ is an expanding algebraic integer.
Since $C>0$, the set $\mathcal{Q}$ is non-empty. Any element
$x=b+q\in\mathbb{Z}[\beta]$ with $b\in\mathcal{B}$ and $q\in\mathcal{Q}$ can
be written as $x=a+\beta q^{\prime}$ for some $a\in\mathcal{A}$ and
$q^{\prime}\in\mathbb{Z}[\beta]$, due to the presence of at least one
representative of each congruence class modulo $\beta$ in $\mathcal{A}$. Using
the isomorphism $\pi$ and Lemma 5.2, we may write
$\pi(q^{\prime})=S^{-1}_{\beta}\cdot\pi(b-a+q)$. We prove that $q^{\prime}$ is
in $\mathcal{Q}$:

$\displaystyle\left\lVert q^{\prime}\right\rVert_{\beta}$
$\displaystyle=\left\lVert\pi\left(q^{\prime}\right)\right\rVert_{S_{\beta}}=\left\lVert
S^{-1}_{\beta}\cdot\pi\left(b-a+q\right)\right\rVert_{S_{\beta}}\leq{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|S^{-1}_{\beta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{S_{\beta}}\left\lVert
b-a+q\right\rVert_{\beta}$
$\displaystyle\leq\frac{1}{|\gamma|}\left(\left\lVert
b-a\right\rVert_{\beta}+\left\lVert
q\right\rVert_{\beta}\right)\leq\frac{1}{|\gamma|}\left(C+R\right)=\frac{C}{|\gamma|}\left(1+\frac{1}{|\gamma|-1}\right)=R\,.$

Hence $q^{\prime}\in\mathcal{Q}$, and thus
$x=b+q\in\mathcal{A}+\beta\mathcal{Q}$. Since there are only finitely many
elements of $\mathbb{Z}^{d}$ bounded by the constant $R$, the set
$\mathcal{Q}$ must be finite. ∎

The way how candidates for the weight coefficients are chosen at line 5 in
Algorithm 1 is the same as in the proof of Lemma 5.6. Therefore, the
convergence of Phase 1 is guaranteed by the following theorem.

######  Theorem 5.7.

Let $\beta\in\mathbb{C}$ be an algebraic integer. Let
$\mathcal{A}\subset\mathbb{Z}[\beta]$ be an alphabet containing at least one
representative of each congruence class modulo $\beta$ in $\mathbb{Z}[\beta]$,
and let $\mathcal{B}\subset\mathbb{Z}[\beta]$ be an input alphabet. If $\beta$
is expanding, then Phase 1 of the Extending Window Method converges.

###### Proof.

Let $R>0$ be the constant and $\mathcal{Q}\subset\mathbb{Z}[\beta]$ the finite
set from (10) in Lemma 5.6, for the alphabet $\mathcal{A}$ and the input
alphabet $\mathcal{B}$. We prove by induction that all intermediate weight
coefficient sets $\mathcal{Q}_{k}$ in Algorithm 1 are subsets of the finite
set $\mathcal{Q}$. Let us start with $\mathcal{Q}_{0}=\\{0\\}$, whose elements
are bounded by any positive constant. Suppose that the intermediate weight
coefficients set $\mathcal{Q}_{k}$ has elements bounded by the constant $R$.
We see from the proof of Lemma 5.6 that the candidates for the set
$\mathcal{Q}_{k+1}$ obtained in $C_{x}$ at line 5 of Algorithm 1 are also
bounded by $R$. Thus, the next intermediate weight coefficients set
$\mathcal{Q}_{k+1}$ has elements bounded by the constant $R$ as well, i.e.,
$\mathcal{Q}_{k+1}\subset\mathcal{Q}$. Since $\\#\mathcal{Q}$ is finite and
$\mathcal{Q}_{0}\subsetneq\mathcal{Q}_{1}\subsetneq\mathcal{Q}_{2}\subsetneq\cdots\subset\mathcal{Q}$,
the Phase 1 successfully ends once we obtain
$\mathcal{Q}_{k}=\mathcal{Q}_{k+1}$. ∎

###  5.2 Convergence of Phase 2

We do not have any straightforward conditions, sufficient or necessary, for
convergence of Phase 2 of the EWM, based on properties of the base $\beta$ or
alphabet $\mathcal{A}$. Nevertheless, the non-convergence can be controlled
during the course of the algorithm. An easy check of non-convergence can be
done by finding the weight coefficient sets $\mathcal{Q}_{[b,\dots,b]}$ for
each $b\in\mathcal{B}$. For that purpose, we introduce a notion of so-called
_stable Phase 2_ , which is then used also in the main result of this section:
the control of non-convergence during Phase 2 is transformed into searching
for a cycle in a directed graph.

Firstly, we mention several equivalent conditions of non-convergence of Phase
2:

######  Lemma 5.8.

The following statements are equivalent for the EWM applied on a numeration
system $(\beta,\mathcal{A})$ and an input alphabet $\mathcal{B}$:

  1. i)

Phase 2 of the EWM does not converge;

  2. ii)

$(\forall\,k\in\mathbb{N})\,(\exists\,(w_{0},\dots,w_{-k})\in\mathcal{B}^{k+1})\,(\\#\mathcal{Q}_{[w_{0},\dots,w_{-k}]}\geq
2)$;

  3. iii)

$(\exists\,(w_{-j})_{j\geq
0}\in\mathcal{B}^{\mathbb{N}})(\exists\,k_{0}\in\mathbb{N})(\forall k\geq
k_{0})(\\#\mathcal{Q}_{[w_{0},\dots,w_{-k}]}=\\#\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}\geq
2)$.

###### Proof.

i)$\iff$ii): The while loop in Algorithm 3 ends if and only if there is
$k\in\mathbb{N}$ such that $\\#\mathcal{Q}_{[w_{0},\dots,w_{-k}]}=1$ for all
$(w_{0},\dots,w_{-k})\in\mathcal{B}^{k+1}$.
ii)$\iff$iii): For $\Rightarrow$, there is an infinite sequence
$(w_{-j})_{j\geq 0}$ such that $\\#\mathcal{Q}_{[w_{0},\dots,w_{-k}]}\geq 2$
for all $k\in\mathbb{N}$, since
$\mathcal{Q}_{[w_{0},\dots,w_{-k}]}\supset\mathcal{Q}_{[w_{0},\dots,w_{-(k+1)}]}$.
Hence, the sequence of integers
$(\\#\mathcal{Q}_{[w_{0},\dots,w_{-k}]})_{k\geq 0}$ is eventually constant.
The opposite implication is trivial. ∎

We need to ensure that the choice of a possible weight coefficients set
$\mathcal{Q}_{[w_{0},\dots,w_{-k}]}\subset\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}$
is determined by the input digits $(w_{0},\ldots,w_{-k})\in\mathcal{B}^{k+1}$
and the set $\mathcal{Q}_{[w_{-1},\dots,w_{-k}]}$, while the influence of the
set $\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}$ is limited. This is formalized in
the following definition:

######  Definition 5.9.

Let $\mathcal{B}$ be an alphabet of input digits. We say that _Phase 2_ of the
EWM is _stable_ if

$\mathcal{Q}_{[w_{-1},\dots,w_{-k}]}=\mathcal{Q}_{[w_{-1},\dots,w_{-(k-1)}]}\implies\mathcal{Q}_{[w_{0},\dots,w_{-k}]}=\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}$

for all $k\in\mathbb{N},k\geq 2$ and for all
$(w_{0},\dots,w_{-k})\in\mathcal{B}^{k+1}$.

Although this definition may seem restrictive, it is actually a natural way
how an algorithm should be designed. The set
$\mathcal{Q}_{[w_{0},\dots,w_{-k}]}$ is constructed so that

$\mathcal{B}+\mathcal{Q}_{[w_{-1},\dots,w_{-k}]}\subset\mathcal{A}+\beta\mathcal{Q}_{[w_{0},\dots,w_{-k}]}\,,$

i.e., there is no reason to choose the set
$\mathcal{Q}_{[w_{0},\dots,w_{-k}]}$ as a proper subset of
$\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}$, as we know that

$\mathcal{B}+\underbrace{\mathcal{Q}_{[w_{-1},\dots,w_{-(k-1)}]}}_{=\mathcal{Q}_{[w_{-1},\dots,w_{-k}]}}\subset\mathcal{A}+\beta\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}\,,$

and $\mathcal{Q}_{[w_{-1},\dots,w_{-(k-1)}]}$ was chosen as sufficient. In
other words, if $\mathcal{Q}_{[w_{0},\dots,w_{-k}]}$ is a proper subset of
$\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}$, then the set
$\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}$ could have been chosen as
$\mathcal{Q}_{[w_{0},\dots,w_{-k}]}$ in the previous iteration step already.

We may guarantee that Phase 2 is stable by wrapping any way of choice of the
set $\mathcal{Q}_{[w_{0},\dots,w_{-k}]}$ into a simple while loop, see [12]
for details.

Now we use the fact that finiteness of Phase 2 implies existence of a length
$m\in\mathbb{N}$ such that, for every $b\in\mathcal{B}$, the set
$\mathcal{Q}_{[\scriptstyle b]}^{\scriptstyle m}$ contains only one element;
where $\mathcal{Q}_{[\scriptstyle b]}^{\scriptstyle m}$ is a shorter notation
for $\mathcal{Q}_{[\underbrace{\scriptstyle b,\dots,b}_{m}]}\,.$ The following
theorem shows that $\\#\mathcal{Q}_{[\scriptstyle b]}^{\scriptstyle m}$ must
decrease every time we increase the length $m$, otherwise Phase 2 does not
converge.

######  Theorem 5.10.

If $m_{0}\in\mathbb{N}$ and $b\in\mathcal{B}$ are such that the sets
$\mathcal{Q}_{[\scriptstyle b]}^{\scriptstyle m_{0}}$ and
$\mathcal{Q}_{[\scriptstyle b]}^{\scriptstyle m_{0}-1}$ produced by a stable
Phase 2 of the EWM have the same size, then

$\\#\mathcal{Q}_{[\scriptstyle b]}^{\scriptstyle
m}=\\#\mathcal{Q}_{[\scriptstyle b]}^{\scriptstyle m_{0}}\qquad\mathrm{\quad
for\ every\quad}m\geq m_{0}-1\,.$

Particularly, if $\\#\mathcal{Q}_{[\scriptstyle b]}^{\scriptstyle m_{0}}\geq
2$, then the Phase 2 of the EWM does not converge.

###### Proof.

As $\mathcal{Q}_{[\scriptstyle b]}^{\scriptstyle
m_{0}}\subset\mathcal{Q}_{[\scriptstyle b]}^{\scriptstyle m_{0}-1}$, the
assumption of the same size implies $\mathcal{Q}_{[\scriptstyle
b]}^{\scriptstyle m_{0}}=\mathcal{Q}_{[\scriptstyle b]}^{\scriptstyle
m_{0}-1}\,.$ By the assumption that Phase 2 is stable, we have

$\mathcal{Q}_{[\scriptstyle b]}^{\scriptstyle
m_{0}}=\mathcal{Q}_{[\scriptstyle b]}^{\scriptstyle
m_{0}-1}\quad\implies\quad\mathcal{Q}_{[\scriptstyle b]}^{\scriptstyle
m_{0}+1}=\mathcal{Q}_{[\scriptstyle b]}^{\scriptstyle
m_{0}}\quad\implies\quad\mathcal{Q}_{[\scriptstyle b]}^{\scriptstyle
m_{0}+2}=\mathcal{Q}_{[\scriptstyle b]}^{\scriptstyle
m_{0}+1}\quad\implies\quad\cdots$

This implies the statement. If $\\#\mathcal{Q}_{[\scriptstyle
b]}^{\scriptstyle m_{0}}\geq 2$, then statement iii) in Lemma 5.8 holds for
the sequence $(b)_{j\geq 0}$. ∎

We use this result as follows: For all input digits $b\in\mathcal{B}$, we run
Algorithm 3 limited only to $k$-tuples $(b,\ldots,b)\in\mathcal{B}^{k}$. In
every iteration $k$, we check whether $\mathcal{Q}_{[\scriptstyle
b]}^{\scriptstyle k}$ is smaller than $\mathcal{Q}_{[\scriptstyle
b]}^{\scriptstyle k-1}$. If not, then it does not converge for the input
$b\cdots b$, and hence the original EWM with input alphabet $\mathcal{B}$ does
not converge either. This check is linear in the length of the window, and
thus it is fast.

In general, it happens that
$\mathcal{Q}_{[w_{0},\dots,w_{-k}]}=\mathcal{Q}_{[w_{0},\dots,w_{-(k-1)}]}$
for some combination of input digits
$(w_{0},\dots,w_{-k})\in\mathcal{B}^{k+1}$, and Phase 2 of the EWM still does
converge. Thus, a condition which signifies non-convergence during Phase 2 is
more complicated. It can be formulated as searching for an infinite path in a
so-called _Rauzy graph_ :

######  Definition 5.11.

Let $\mathcal{B}$ be an alphabet of input digits, and let Phase 2 of the EWM
be stable. Consider $k\in\mathbb{N},k\geq 2$. We set

$\displaystyle V_{k}$
$\displaystyle:=\left\\{(w_{-1},\dots,w_{-k})\in\mathcal{B}^{k}\colon\\#\mathcal{Q}_{[w_{-1},\dots,w_{-k}]}=\\#\mathcal{Q}_{[w_{-1},\dots,w_{-(k-1)}]}\right\\}\,\mathrm{and}$
$\displaystyle E_{k}$
$\displaystyle:=\left\\{(w_{-1},\dots,w_{-k})\rightarrow(w^{\prime}_{-1},\dots,w^{\prime}_{-k})\in
V_{k}\times
V_{k}\colon\vphantom{(w^{\prime}_{-1},\dots,w^{\prime}_{-(k-1)})}\right.$
$\displaystyle\qquad\qquad\qquad\qquad\left.(w_{-2},\dots,w_{-k})=(w^{\prime}_{-1},\dots,w^{\prime}_{-(k-1)})\right\\}\,.$

The directed graph _$G_{k}=(V_{k},E_{k})$_ is called _Rauzy graph of Phase 2
(for the length $k$)_.

This term comes from combinatorics on words. The vertices of the Rauzy graph
$G_{k}$ are combinations of input digits for which the size of their possible
weight coefficients sets did not decrease with an increment of the length $k$;
whereas in combinatorics on words, the vertices are given as factors of some
language. But the directed edges are placed in the same manner – if some
combination of digits without the first digit equals another combination
without the last digit.

The structure of the Rauzy graph $G_{k}$ signifies whether the non-decreasing
combinations are such that they cause non-convergence of Phase 2. Existence of
an infinite walk in $G_{k}$ implies that Phase 2 does not converge:

######  Theorem 5.12.

Let Phase 2 of the EWM be stable. If there exists
$k_{0}\in\mathbb{N},k_{0}\geq 2$, and
$(w_{0},\dots,w_{-k_{0}})\in\mathcal{B}^{k_{0}+1}$ such that

  1. i)

$\\#\mathcal{Q}_{[w_{0},\dots,w_{-(k_{0}-1)}]}>1$ and

  2. ii)

there is an infinite walk $((w^{(i)}_{-1},\dots,w^{(i)}_{-k_{0}}))_{i\geq 1}$
in $G_{k_{0}}$ starting in the vertex
$(w^{(1)}_{-1},\dots,w^{(1)}_{-k_{0}})=(w_{-1},\dots,w_{-k_{0}})\,,$

then Phase 2 does not converge.

###### Proof.

Let us set $(w_{k})_{k\geq
0}:=w_{0},w_{1}^{(1)},\dots,w^{(1)}_{k_{0}-1},w^{(1)}_{k_{0}},w_{k_{0}}^{(2)},w_{k_{0}}^{(3)},w_{k_{0}}^{(4)},\dots$;
and we prove that

$\\#\mathcal{Q}_{[w_{0},\dots,w_{-k}]}=\\#\mathcal{Q}_{[w_{0},\dots,w_{-(k_{0}-1)}]}>1\mathrm{\quad
for\ all\quad}k\geq k_{0}-1\,,$

so the condition iii) in Lemma 5.8 is satisfied. Let $\ell\in\mathbb{N}$.
Since $(w_{-(1+\ell)},\dots,w_{-(k_{0}+\ell)})$ is a vertex of $G_{k_{0}}$,
the set $\mathcal{Q}_{[w_{-\ell},\dots,w_{-(k_{0}+\ell)}]}$ equals
$\mathcal{Q}_{[w_{-\ell},\dots,w_{-(k_{0}+\ell-1)}]}$. As Phase 2 is stable,
we have

$\displaystyle\mathcal{Q}_{[w_{-\ell},\dots,w_{-(k_{0}+\ell)}]}=\mathcal{Q}_{[w_{-\ell},\dots,w_{-(k_{0}+\ell-1)}]}$
$\displaystyle\implies\quad$
$\displaystyle\mathcal{Q}_{[w_{-(\ell-1)},\dots,w_{-(k_{0}+\ell)}]}=\mathcal{Q}_{[w_{-(\ell-1)},\dots,w_{-(k_{0}+\ell-1)}]}$
$\displaystyle\quad\vdots$ $\displaystyle\implies\quad$
$\displaystyle\mathcal{Q}_{[w_{-1},\dots,w_{-(k_{0}+\ell)}]}=\mathcal{Q}_{[w_{-1},\dots,w_{-(k_{0}+\ell-1)}]}$
$\displaystyle\implies\quad$
$\displaystyle\mathcal{Q}_{[w_{0},\dots,w_{-(k_{0}+\ell)}]}=\mathcal{Q}_{[w_{0},\dots,w_{-(k_{0}+\ell-1)}]}\,.$

Hence,
$\\#\mathcal{Q}_{[w_{0},\dots,w_{-k}]}=\\#\mathcal{Q}_{[w_{0},\dots,w_{-(k_{0}-1)}]}>1$
for all $k\geq k_{0}-1$. ∎

Let us remark that existence of an infinite walk in a finite graph is
equivalent to existence of a cycle in the graph. Thus, if there is an infinite
walk, we may find another one whose sequence of vertices is eventually
periodic. This fact can be used for revealing non-convergence of Phase 2
during its run. Namely, in $k$-th iteration, we construct the Rauzy graph
$G_{k+1}$ and check whether there is an infinite walk in $G_{k}$ starting in
$(w_{-1},\dots,w_{-k_{0}})$. This modification of Phase 2 is elaborated in
[12].

##  6 Implementation of Extending Window Method

We implement the Extending Window Method (EWM) in a more general setting than
explained above. Let $\omega$ be an algebraic integer. Parallel addition is
searched for a numeration system $(\beta,\mathcal{A})$ such that
$\beta\in\mathbb{Z}[\omega]$ and $\mathcal{A}\subset\mathbb{Z}[\omega]$. All
elements of $\mathbb{Z}[\omega]$ are algebraic integers, since $\omega$ is an
algebraic integer, and clearly $\mathbb{Z}[\beta]\subset\mathbb{Z}[\omega]$.
We run the EWM just as described above, but all steps being now computed in
$\mathbb{Z}[\omega]$, instead of $\mathbb{Z}[\beta]$.

Let us remark that, for instance, the necessary condition from Theorem 2.4,
that $\mathcal{A}$ must contain all representatives modulo $\beta-1$, is not
valid in $\mathbb{Z}[\omega]$ anymore, since congruence classes in
$\mathbb{Z}[\omega]$ and $\mathbb{Z}[\beta]$ are different if
$\mathbb{Z}[\beta]\subsetneq\mathbb{Z}[\omega]$ – see the discussion in
conclusion of [14]. Nevertheless, the statements in Theorem 5.1 ($\beta$ must
be expanding), Theorem 5.7 (convergence of Phase 1), and Theorems 5.10 and
5.12 (control of convergence of Phase 2) can be proven also for
$\mathbb{Z}[\omega]$, see [12].

Our implementation of the EWM in SageMath can be downloaded from [13]. User
information is provided in `readme.md`, and more details about the
implementation can be found also in [12]. We remark that the program allows to
choose an algebraic integer $\omega$ by means of its minimal polynomial
$m_{\omega}$, then the base $\beta\in\mathbb{Z}[\omega]$ and the alphabet
$\mathcal{A}\subset\mathbb{Z}[\omega]$. An input alphabet
$\mathcal{B}\subsetneq\mathcal{A}+\mathcal{A}$ or a block length
$k\in\mathbb{N}$ for $k$-block approach may be specified.

One can also select various methods of choice in Phase 1 and in Phase 2. The
Algorithm 2 above describes methods encoded by `’1b’` (absolute value) and
`’1d’` ($\beta$-norm) for Phase 1. The ways of choice in the Algorithm 4 for
Phase 2 can be selected by `’2b’` (center of gravity) and `’2d’`
($\beta$-norm). Description of other methods available in the program
implementation can be found in [12] or directly in the source code.

Before starting Phase 2, the program checks whether it converges for inputs
consisting of repetition of a single digit $(b,\ldots,b)$, and stops if not,
according to Theorem 5.10. During the computation of Phase 2, Rauzy graphs are
constructed, and the computation stops if the conditions of Theorem 5.12 are
satisfied. In other words, non-finiteness of the EWM can be revealed by these
checks.

Results of the program for selected examples from Section 7 are available at
[15]. Various combinations of methods in Phase 1 and Phase 2 are included.
Log-files provide information about the course of the computations, and the
resulting weight functions $q$ are stored in CSV format when the EWM is
successful.

##  7 Results Obtained by Extending Window Method

This chapter shows selected results of the Extending Window Method (EWM).
Firstly, we focus on numeration systems with parallel addition algorithms
known from previous works of various authors – we investigate whether the EWM
delivers the same algorithms as they have developed manually. Then, we
describe a set of new results – parallel addition algorithms not known so far.

###  7.1 Integer Bases

Let us start with positive integer bases $\beta=b\in\mathbb{N}$, $b\geq 2$,
which certainly are algebraic integers; and they have no algebraic conjugates
other than themselves, so no conjugates of modulus $\leq 1$. We apply the EWM
on (several samples of) numeration systems with these bases, analyzed manually
in previous works:

  * •

A. Avizienis – bases $\beta=b\geq 3$, with (symmetric) alphabet
$\mathcal{A}=\\{-a,\ldots,0,\ldots,a\\}$, using the smallest possible
$a=\lceil(\beta+1)/2\rceil$: The EWM provides the same parallel addition
algorithms as introduced by A. Avizienis in [1]. This was tested on a sample
of numeration systems $(3,\\{-2,\ldots,+2\\})$, $(4,\\{-3,\ldots,+3\\})$,
$(7,\\{-4,\ldots,+4\\})$, or $(10,\\{-6,\ldots,+6\\})$; and the pattern of the
resulting parallel addition algorithms shows that the EWM would work
analogously and correctly, using any positive integer $\beta\in\mathbb{N}$,
$\beta\geq 3$. The key parameters of the parallel addition algorithms obtained
here are as follows:

    * –

weight coefficients $q_{j}=q_{j}(w_{j})\in\mathcal{Q}=\\{0,\pm 1\\}$ depend on
one position only, and thus

    * –

digits of the sum $z_{j}=z_{j}(w_{j},q_{j},q_{j-1})=z_{j}(w_{j},w_{j-1})$ are
$2$-local function, with memory $r=1$.

  * •

C. Y. Chow, J. E. Robertson – even bases $\beta=b=2a$ with $a\in\mathbb{N}$,
$a\geq 1$, and with (symmetric) alphabet
$\mathcal{A}=\\{-a,\ldots,0,\ldots,a\\}$: Again, the EWM delivers the same
parallel addition algorithms as published earlier in [2] by Chow & Robertson
for the tested sample of numeration systems $(2,\\{-1,0,+1\\})$,
$(4,\\{-2,\ldots,+2\\})$ or $(10,\\{-5,\ldots,+5\\})$, and would do the same
with any positive even base $\beta=2a$. The key parameters of these parallel
addition algorithms are as follows:

    * –

weight coefficients $q_{j}=q_{j}(w_{j},w_{j-1})\in\mathcal{Q}=\\{0,\pm 1\\}$
depend on two positions (due to smaller $\\#\mathcal{A}$),

    * –

digits of the sum
$z_{j}=z_{j}(w_{j},q_{j},q_{j-1})=z_{j}(w_{j},w_{j-1},w_{j-2})$ are $3$-local
function, with memory $r=2$.

  * •

B. Parhami – any positive integer base $\beta\geq 2$, with alphabet
$\mathcal{A}=\\{-d,\ldots,0,\ldots,b-d\\}$, $0\leq d\leq b$, of the minimal
size $\\#\mathcal{A}=\beta+1$ for parallel addition: Algorithms published in
[17, 5] for these numeration systems are now obtained equally also by the EWM,
for any choice of $d\in\\{0,\ldots,b\\}$, i.e., for all shapes of alphabets in
question (positive or negative or mixed, symmetric or non-symmetric). This was
tested explicitly on numeration systems $(2,\\{0,1,2\\})$,
$(3,\\{-1,\ldots,2\\})$, $(4,\\{-3,\ldots,+1\\})$, or
$(7,\\{-4,\ldots,+3\\})$, and works in general, with parameters:

    * –

weight coefficients $q_{j}=q_{j}(w_{j},w_{j-1})\in\mathcal{Q}=\\{0,\pm 1\\}$
or $\mathcal{Q}=\\{0,1,2\\}$ or $\mathcal{Q}=\\{-2,-1,0\\}$, depending on two
positions (due to the minimal alphabet size $\\#\mathcal{A}$ for parallel
addition),

    * –

digits of the sum
$z_{j}=z_{j}(w_{j},q_{j},q_{j-1})=z_{j}(w_{j},w_{j-1},w_{j-2})$ are $3$-local
function, with memory $r=2$.

  * •

Also for negative integer bases $\beta=-b\in\mathbb{Z}$, $b\geq 2$, we can
apply the EWM, because they are algebraic integers without conjugates of
modulus $\leq 1$. Again, we focus on alphabets
$\mathcal{A}=\\{-d,\ldots,0,\ldots,b-d\\}$, $0\leq d\leq b$, of the minimal
size $\\#\mathcal{A}=b+1$ for parallel addition. Testing was done on
numeration systems $(-2,\\{0,1,2\\})$, $(-3,\\{-1,\ldots,2\\})$,
$(-4,\\{-3,\ldots,+1\\})$, or $(-7,\\{-4,\ldots,+3\\})$; and also here the EWM
produced the same algorithms as derived manually earlier in [5], with
parameters:

    * –

weight coefficients $q_{j}=q_{j}(w_{j},w_{j-1})\in\mathcal{Q}=\\{0,\pm 1\\}$
or $\mathcal{Q}=\\{0,1,2\\}$ or $\mathcal{Q}=\\{-2,-1,0\\}$, depending on two
positions (due to the minimal alphabet size $\\#\mathcal{A}$ for parallel
addition),

    * –

digits of the sum
$z_{j}=z_{j}(w_{j},q_{j},q_{j-1})=z_{j}(w_{j},w_{j-1},w_{j-2})$ are $3$-local
function, with memory $r=2$.

Table 1 summarizes these results, together with the basic parameters of the
respective numeration systems and parallel addition algorithms.

Base | Minimal | Alphabet | Alphabet | Locality | Same
---|---|---|---|---|---
$\beta$ | polynomial $m_{\beta}$ | $\mathcal{A}$ | size $\\#\mathcal{A}$ | $p=1+r$ | alg. as
Avizienis | $X-b$ | $\\{-a,\ldots,a\\}$ | $\\#\mathcal{A}=2\lfloor\frac{\beta}{2}\rfloor+3$ | $p=2$ | [1]
$\beta=b,b\geq 3,b\in\mathbb{N}$ | $a=\lceil\frac{b+1}{2}\rceil$ | non-minimal $\\#\mathcal{A}$
Chow & Robertson | $X-2a$ | $\\{-a,\ldots,a\\}$ | $\\#\mathcal{A}=\beta+1$ | $p=3$ | [2]
$\beta=2a,a\in\mathbb{N}$ | minimal $\\#\mathcal{A}$
Parhami | $X-b$ | $\\{-d,\ldots,b-d\\}$ | $\\#\mathcal{A}=\beta+1$ | $p=3$ | [17]
$\beta=b,b\geq 2,b\in\mathbb{N}$ | $0\leq d<b$ | minimal $\\#\mathcal{A}$
negative integer | $X+b$ | $\\{-d,\ldots,b-d\\}$ | $\\#\mathcal{A}=|\beta|+1$ | $p=3$ | [5]
$\beta=-b,b\geq 2,b\in\mathbb{N}$ | $0\leq d<b$ | minimal $\\#\mathcal{A}$
Table 1: ($1$-block) parallel addition algorithms obtained by the Extending
Window Method for numeration systems with integer bases and alphabets are the
same as found earlier by Avizienis, Chow & Robertson, Parhami, or Frougny &
Pelantová & Svobodová.

###  7.2 Real Bases

Selected classes of real bases were elaborated earlier in [5] and [3], where
the parallel addition algorithms are given, even on alphabets of the minimal
size for parallel addition. Some of these bases are not eligible for the EWM,
since they do not fulfil the core conditions for its usage:

  * •

Rational bases $\beta=\pm a/b$ are algebraic numbers, but not algebraic
integers.

  * •

Real bases $\beta$ being quadratic Pisot numbers, i.e., roots of polynomials
$\beta^{2}=a\beta\pm b$, are algebraic integers, but they are not expanding,
as their algebraic conjugates are smaller than $1$ in modulus.

Next, we study other classes of real bases, which are EWM-eligible, being
expanding algebraic integers. In the sequel, we show examples of successful
EWM applications for such bases, and compare thus obtained results – parallel
addition algorithms – with those previously found manually (where available).

####  7.2.1 Real Bases – Roots of Integers

We limit this class of bases to real roots of integers in the so-called
_minimal form_

$\beta=\sqrt[\ell]{b}\quad\mathrm{with}\quad\ell,b\in\mathbb{N},b\geq 2\,,$

where $\beta$ cannot be written as $\beta=\sqrt[\ell^{\prime\prime}]{c}$, with
$\ell=\ell^{\prime}\ell^{\prime\prime}$ and $b=c^{\ell^{\prime}}$, for any
$\ell^{\prime},\ell^{\prime\prime},c\in\mathbb{N}$, $\ell^{\prime}>1$.

Parallel addition algorithms – as $1$-block $(2\ell+1)$-local functions – were
obtained manually in [5] for such bases with alphabets
$\mathcal{A}=\\{0,\ldots,b\\}$ of the minimal possible size
$\\#\mathcal{A}=b+1$. Also the automated EWM is able to find ($1$-block)
parallel addition algorithms for these numeration systems
$(\beta,\mathcal{A})$, see selected examples in Table 2. The EWM-results on
these examples lead to a hypothesis that, for base $\beta=\sqrt[\ell]{b}$ and
alphabet $\mathcal{A}=\\{0,\ldots,b\\}$, the size of the weight coefficients
set obtained during Phase 1 of the EWM is $\\#\mathcal{Q}=3^{\ell}$, and that
the $p$-locality of the parallel addition function resulting after Phase 2 is
$p=2\ell+1$. That is the same $p$-locality as in the parallel addition
algorithms provided for these numeration systems in [5], nevertheless, the
complexity of the algorithms constructed via EWM is a lot higher than of those
proposed manually in [5].

Base | Minimal | Alphabet | Alphabet | Weight coefficients | Locality
---|---|---|---|---|---
$\beta$ | polynomial $m_{\beta}$ | $\mathcal{A}$ | size $\\#\mathcal{A}$ | set size $\\#\mathcal{Q}$ | $p=1+r$
$\beta=\sqrt[2]{2}$ | $X^{2}-2$ | $\\{0,\ldots,2\\}$ | $\\#\mathcal{A}=3$ | $\\#\mathcal{Q}=9$ | $p=5$
$\beta=\sqrt[2]{3}$ | $X^{2}-3$ | $\\{0,\ldots,3\\}$ | $\\#\mathcal{A}=4$ | $\\#\mathcal{Q}=9$ | $p=5$
$\beta=\sqrt[2]{5}$ | $X^{2}-5$ | $\\{0,\ldots,5\\}$ | $\\#\mathcal{A}=6$ | $\\#\mathcal{Q}=9$ | $p=5$
$\beta=\sqrt[2]{13}$ | $X^{2}-13$ | $\\{0,\ldots,13\\}$ | $\\#\mathcal{A}=14$ | $\\#\mathcal{Q}=9$ | $p=5$
$\beta=\sqrt[2]{17}$ | $X^{2}-17$ | $\\{0,\ldots,17\\}$ | $\\#\mathcal{A}=18$ | $\\#\mathcal{Q}=9$ | $p=5$
$\beta=\sqrt[2]{21}$ | $X^{2}-21$ | $\\{0,\ldots,21\\}$ | $\\#\mathcal{A}=22$ | $\\#\mathcal{Q}=9$ | $p=5$
$\beta=\sqrt[3]{2}$ | $X^{3}-2$ | $\\{0,\ldots,2\\}$ | $\\#\mathcal{A}=3$ | $\\#\mathcal{Q}=27$ | $p=7$
$\beta=\sqrt[3]{7}$ | $X^{3}-7$ | $\\{0,\ldots,7\\}$ | $\\#\mathcal{A}=8$ | $\\#\mathcal{Q}=27$ | $p=7$
$\beta=\sqrt[4]{5}$ | $X^{4}-5$ | $\\{0,\ldots,5\\}$ | $\\#\mathcal{A}=6$ | $\\#\mathcal{Q}=81$ | $p=9$
$\beta=\sqrt[5]{6}$ | $X^{5}-6$ | $\\{0,\ldots,6\\}$ | $\\#\mathcal{A}=7$ | $\\#\mathcal{Q}=243$ | $p=11$
$\beta=\sqrt[\ell]{b}$ | $X^{\ell}-b$ | $\\{0,\ldots,b\\}$ | $\\#\mathcal{A}=b+1$ | hypothesis: | hypothesis:
$b\in\mathbb{N},b\geq 2$ |  |  |  | $\\#\mathcal{Q}=3^{\ell}$ | $p=2\ell+1$
Table 2: ($1$-block) parallel addition algorithms obtained by the Extending
Window Method for selected bases of the form $\beta=\sqrt[\ell]{b}$, with
$\ell,b\in\mathbb{N}$, and non-negative integer alphabets
$\mathcal{A}=\\{0,\ldots,b\\}$ of the minimal size $\\#\mathcal{A}=b+1$ for
parallel addition. The full look-up tables containing the weight coefficients
$q_{j}=q_{j}(w_{j},w_{j-1},\ldots,w_{j-(2\ell-1)})$, assigned to all necessary
$2\ell$-tuples of digits $w_{j}\in\mathcal{A}+\mathcal{A}$, are published in
[15]. In several cases, we use a smaller input set
$\mathcal{B}\subsetneq\mathcal{A}+\mathcal{A}$, in order to decrease the size
of the look-up tables of weight coefficients.

####  7.2.2 Real Quadratic Bases

For some real quadratic bases (other than the classes already described
above), we consider non-integer alphabets, and apply the EWM on such
numeration systems. It is successful – the EWM does provide parallel addition
algorithms for those systems, and even on alphabets of minimal size. See Table
3 for a selection of such results.

Base | Minimal | Alphabet | Weight coefficients | Locality
---|---|---|---|---
$\beta$ | polynomial $m_{\beta}$ | size $\\#\mathcal{A}$ | set size $\\#\mathcal{Q}$ | $p=1+r$
$\beta=\frac{1}{2}\sqrt{17}-\frac{9}{2}$ | $x^{2}+9x+16$ | $\\#\mathcal{A}=26$ | $\\#\mathcal{Q}=17$ | $p=6$
$\beta=\sqrt{5}-5$ | $x^{2}+10x+20$ | $\\#\mathcal{A}=31$ | $\\#\mathcal{Q}=11$ | $p=4$
$\beta=\frac{3}{2}\sqrt{5}-\frac{15}{2}$ | $x^{2}+15x+45$ | $\\#\mathcal{A}=61$ | $\\#\mathcal{Q}=15$ | $p=4$
Table 3: ($1$-block) parallel addition algorithms obtained by the Extending
Window Method for selected real quadratic bases, using non-integer alphabets
of the minimal size $\\#\mathcal{A}=\min\\{|m_{\beta}(0)|,|m_{\beta}(1)|\\}$
for parallel addition. The full look-up tables containing the weight
coefficients $q_{j}=q_{j}(w_{j},w_{j-1},\ldots,w_{j-(r-1)})$, assigned to all
necessary $r$-tuples of digits $w_{j}\in\mathcal{A}+\mathcal{A}$, are
published in [15].

###  7.3 Complex Bases

It is in the area of numeration systems with complex bases that the EWM
provides the most interesting new results, which would be extremely laborious
(if not impossible) to achieve by manual calculation.

####  7.3.1 Complex Quadratic Bases

Table 4 shows selected results of the EWM for numeration systems with complex
quadratic bases with non-integer alphabets. These results were obtained via
methods 1d and 2b in our EWM-implementation. All results, including also other
methods, can be found in [15].

Base | Minimal | Alphabet | Weight coefficients | Locality
---|---|---|---|---
$\beta$ | polynomial $m_{\beta}$ | size $\\#\mathcal{A}$ | set size $\\#\mathcal{Q}$ | $p=1+r$
$\beta=-\imath\sqrt{11}-4$ | $x^{2}+8x+27$ | $\\#\mathcal{A}=36$ | $\\#\mathcal{Q}=13$ | $p=8$
$\beta=\imath\sqrt{11}-4$ | $x^{2}+8x+27$ | $\\#\mathcal{A}=36$ | $\\#\mathcal{Q}=13$ | $p=6$
$\beta=\frac{1}{2}\imath\sqrt{11}-\frac{7}{2}$ | $x^{2}+7x+15$ | $\\#\mathcal{A}=23$ | $\\#\mathcal{Q}=13$ | $p=6$
$\beta=\frac{1}{2}\imath\sqrt{7}-\frac{1}{2}$ | $x^{2}+x+2$ | $\\#\mathcal{A}=4$ | $\\#\mathcal{Q}=29$ | $p=9$
$\beta=\imath\sqrt{7}-4$ | $x^{2}+8x+23$ | $\\#\mathcal{A}=32$ | $\\#\mathcal{Q}=10$ | $p=6$
$\beta=-\frac{3}{2}\imath\sqrt{3}-\frac{15}{2}$ | $x^{2}+15x+63$ | $\\#\mathcal{A}=79$ | $\\#\mathcal{Q}=13$ | $p=4$
$\beta=-\frac{3}{2}\imath\sqrt{3}-\frac{9}{2}$ | $x^{2}+9x+27$ | $\\#\mathcal{A}=37$ | $\\#\mathcal{Q}=13$ | $p=3$
$\beta=\imath\sqrt{2}-3$ | $x^{2}+6x+11$ | $\\#\mathcal{A}=18$ | $\\#\mathcal{Q}=15$ | $p=5$
$\beta=-2\imath-4$ | $x^{2}+8x+20$ | $\\#\mathcal{A}=29$ | $\\#\mathcal{Q}=11$ | $p=3$
$\beta=-3\imath-3$ | $x^{2}+6x+18$ | $\\#\mathcal{A}=25$ | $\\#\mathcal{Q}=15$ | $p=5$
Table 4: For the class of numeration systems with complex quadratic bases
allowing parallel addition with non-integer alphabets, we provide here a
selection from the Extending Window Method results, where the ($1$-block)
parallel addition algorithms were obtained on alphabets of minimal size
$\\#\mathcal{A}$ for parallel addition.

####  7.3.2 Complex Bases – Roots of Integers

Here we focus on bases of the type $\beta=\sqrt[\ell]{-b}$, with
$\ell,b\in\mathbb{N}$, $b\geq 2$.

For some of these bases, e.g $\beta=\imath\sqrt{2}=\sqrt[2]{-2}$ or the so-
called Knuth base $\beta_{K}=2\imath=\sqrt[2]{-4}$, the parallel addition
algorithms were already provided in [5], using non-negative integer alphabets
of the minimal size. Those algorithms are given by quite simple formulas,
where $q_{j}=q_{j}(w_{j},w_{j-2})$ and $z_{j}=z_{j}(w_{j},q_{j},q_{j-2})$, so
$z_{j}=z_{j}(w_{j},w_{j-2},w_{j-4})$. Such formulas are formally $5$-local
functions (with memory $r=4$), but using only every second position.
Therefore, we could actually process all odd positions and all even positions
separately, via just $3$-local functions (with memory $r=2$) in each part.
When using the EWM on these examples of bases, we also obtain parallel
addition algorithms, even for various integer alphabets of minimal size (so
not just for non-negative ones); but their formulas are not so simple,
although their $p$-locality parameters are the same, i.e., $p=5$ with memory
$r=4$. For non-integer alphabets, however, the EWM does not provide any new
results:

  * •

Base $\beta=\imath\sqrt{2}=\sqrt[2]{-2}$, with minimal polynomial
$m_{\beta}(X)=X^{2}+2$, needs the minimal alphabet size for parallel addition
equal to
$\\#\mathcal{A}=3=\max\\{2,3\\}=\max\\{|m_{\beta}(0)|,|m_{\beta}(1)|\\}$. The
EWM acts as follows:

    * –

On integer alphabets $\mathcal{A}=\\{0,1,2\\}$ or $\mathcal{A}=\\{-1,0,1\\}$:
EWM provides parallel addition algorithms with weight coefficients
$q_{j}=q_{j}(w_{j},w_{j-1},w_{j-2},w_{j-3})$, i.e., memory $r=4$, and
consequently a $5$-local addition function
$z_{j}=z_{j}(w_{j},q_{j},q_{j-1})=z_{j}(w_{j},\ldots,w_{j-4})$.

    * –

On non-integer alphabets $\mathcal{A}=\\{0,1,1+\imath\sqrt{2}\\}$ or
$\mathcal{A}=\\{0,1,-\imath\sqrt{2}\\}$: EWM gets cycled in Phase 2, so no new
parallel addition algorithm is obtained here.

  * •

Knuth base $\beta_{K}=2\imath=\sqrt[2]{-4}$, with minimal polynomial
$m_{\beta}(X)=X^{2}+4$, has the minimal alphabet size for parallel addition
$\\#\mathcal{A}=5=\max\\{4,5\\}=\max\\{|m_{\beta}(0)|,|m_{\beta}(1)|\\}$. The
EWM ends up as follows:

    * –

On integer alphabets $\mathcal{A}=\\{0,\ldots,4\\}$ or
$\mathcal{A}=\\{-1,\ldots,3\\}$ or $\mathcal{A}=\\{-2,\ldots,2\\}$: EWM
results in parallel addition algorithms with memory $r=4$ due to weight
coefficients $q_{j}=q_{j}(w_{j},w_{j-1},w_{j-2},w_{j-3})$, and thus $p=5$ for
$z_{j}=z_{j}(w_{j},q_{j},q_{j-1})=z_{j}(w_{j},\ldots,w_{j-4})$, i.e., a
$5$-local function for the digits of the sum.

    * –

On non-integer alphabets, e.g.
$\mathcal{A}=\\{0,1+2\imath,-1-2\imath,2-2\imath,-2+2\imath\\}$: no parallel
addition algorithm obtained by EWM, due to several elements
$b\in\mathcal{A}+\mathcal{A}$, for which there is no unique weight coefficient
for inputs of the form $(b,\ldots,b)$.

For the bases mentioned above, it is not any helpful to use the $k$-block
concept – it does not allow to decrease the alphabet size for parallel
addition. The EWM correctly reports for such attempts that there are not
enough representatives of congruence classes $\mod(\beta-1)$ in the alphabet.

Parameters of the $1$-block parallel addition algorithms for bases
$\beta=\imath\sqrt{2}$ and $\beta=2\imath$ are summarized in Table 5, together
with another two examples: $\beta=-\imath\sqrt{7}$ and
$\beta=-\imath\sqrt{11}$. The latter two are elaborated in two ways – on
alphabets of minimal and non-minimal size, respectively, via $5$-local and
$3$-local functions, respectively.

Base | Minimal | Alphabet | Weight coefficients | Locality | Comment
---|---|---|---|---|---
$\beta$ | polynomial $m_{\beta}$ | size $\\#\mathcal{A}$ | set size $\\#\mathcal{Q}$ | $p=1+r$ |
$\beta=-\imath\sqrt{11}$ | $x^{2}+11$ | $\\#\mathcal{A}=13$ | $\\#\mathcal{Q}=9$ | $p=3$ | non-minimal $\\#\mathcal{A}$
|  | $\\#\mathcal{A}=12$ | $\\#\mathcal{Q}=9$ | $p=5$ | minimal $\\#\mathcal{A}$
$\beta=-\imath\sqrt{7}$ | $x^{2}+7$ | $\\#\mathcal{A}=9$ | $\\#\mathcal{Q}=9$ | $p=3$ | non-minimal $\\#\mathcal{A}$
|  | $\\#\mathcal{A}=8$ | $\\#\mathcal{Q}=9$ | $p=5$ | minimal $\\#\mathcal{A}$
$\beta=\imath\sqrt{2}$ | $x^{2}+2$ | $\\#\mathcal{A}=3$ | $\\#\mathcal{Q}=9$ | $p=5$ | minimal $\\#\mathcal{A}$
$\beta=2\imath$ | $x^{2}+4$ | $\\#\mathcal{A}=5$ | $\\#\mathcal{Q}=9$ | $p=5$ | minimal $\\#\mathcal{A}$
Table 5: ($1$-block) parallel addition algorithms for complex bases of the
type $\beta=\sqrt[\ell]{-b}$, with $\ell,b\in\mathbb{N}$, allowing parallel
addition with integer alphabets. On some of the bases, we illustrate how the
higher (than minimal) number of elements in alphabet $\\#\mathcal{A}$ helps to
decrease the $p$-locality of the parallel addition function.

####  7.3.3 Canonical Number Systems

In the sequel, we investigate in detail another two bases of the type
$\beta=\sqrt[\ell]{-b}$, $b\in\mathbb{N}$:

  * •

Penney base $\beta_{P}=-1+\imath=\sqrt[4]{-4}$: studied in Section 7.4;

  * •

Eisenstein base
$\beta_{E}=-1+\exp{\frac{2\pi\imath}{3}}=\frac{-3+\imath\sqrt{3}}{2}=\sqrt[6]{-27}$:
studied in Section 7.5.

For these bases, the EWM provides a rich set of results – not only regarding
$1$-block parallel addition, but using also the $k$-block concept. Here we
exploit the fact that both these bases form Canonical Number Systems (CNS – as
studied in [9, 10]) and a result from [3], summarized in the following Remark:

######  Remark 7.1.

An algebraic number $\beta$ and the alphabet
$\mathcal{C}=\\{0,1,\ldots,|N(\beta)|-1\\}$, where $N(\beta)$ is the norm of
$\beta$ over $\mathbb{Q}$, form a  _Canonical Number System (CNS)_ , if any
element $X$ of the ring of integers $\mathbb{Z}[\beta]$ has a unique
representation in the form $X=\sum_{k=0}^{n}x_{k}\beta^{k}$, where
$x_{k}\in\mathcal{C}$. In a CNS, block parallel addition is possible on the
alphabet $\mathcal{A}=\\{0,1,\ldots,2|N(\beta)|-2\\}$ or on the alphabet
$\mathcal{A}=\\{-|N(\beta)|+1,\ldots,0,\ldots,|N(\beta)|-1\\}$.

Application of this result on Penney and Eisenstein bases means:

  * •

the norm of Penney base is $N(\beta_{P})=2$, so $(\beta_{P},\mathcal{C}_{P})$
with $\mathcal{C}_{P}=\\{0,1\\}$ is a CNS – therefore, block parallel addition
in base $\beta_{P}$ is possible on alphabets $\mathcal{A}_{P}=\\{-1,0,1\\}$ or
$\mathcal{A}_{P}=\\{0,1,2\\}$;

  * •

the norm of Eisenstein base is $N(\beta_{E})=3$, so
$(\beta_{E},\mathcal{C}_{E})$ with $\mathcal{C}_{E}=\\{0,1,2\\}$ is a CNS –
thus block parallel addition in base $\beta_{E}$ is possible on alphabets
$\mathcal{A}_{E}=\\{-2,-1,0,1,2\\}$ or $\mathcal{A}_{E}=\\{0,1,2,3,4\\}$.

But the length $k$ of blocks for the $k$-block parallel addition is not given
in Remark 7.1 – so we test it via the EWM, proceeding simply from
$k=2,3,\ldots$ upwards. The EWM is successful, and generates the algorithms of
block parallel addition for both Penney and Eisenstein numeration systems,
with $k=2$ and $k=3$, respectively. The alphabets $\mathcal{A}_{P_{2}}$ and
$\mathcal{A}_{E_{3}}$, of sizes $\mathcal{A}_{P_{2}}=3$ and
$\mathcal{A}_{E_{3}}=5$, in these algorithms are exactly those as predicted by
the Remark 7.1; both the symmetric and the non-negative sets of consecutive
integers. In both cases, the $k$-block concept helps to decrease the size of
alphabets for parallel addition by two digits.

Base $\beta$ | Alphabet |  | Block | Locality |
---|---|---|---|---|---
Minimal polynomial $m_{\beta}$ | $\mathcal{A}$ | $\\#\mathcal{A}$ | length | $p=1+r$ | Comment
Penney | $\\{0,\pm 1,\pm\imath\\}$ | $5$ | $k=1$ | $p=7$ | minimal $\\#\mathcal{A}$
$\beta=1-\imath$ | $\\{0,\pm 1\\}$ | $3$ | $k=2$ | $p=6$ | $\\#\mathcal{A}$ proposed in [10]
$m_{\beta}=X^{2}+2X+2$ | $\\{0,1,2\\}$
Eisenstein | $\\{0,\pm 1,\pm\omega,\pm\omega^{2}\\}$ | $7$ | $k=1$ | $p=4$ | minimal $\\#\mathcal{A}$
$\beta=1-\omega,\omega=\exp{\frac{2\pi\imath}{3}}$ | $\\{0,1,\pm\omega,\omega^{2}\\}$ | $5$ | $k=3$ | $p=3$ | $\\#\mathcal{A}$ proposed in [10]
$m_{\beta}=X^{2}+3X+3$
Table 6: Parallel addition algorithms obtained by the Extending Window Method
for the Penney and Eisenstein (complex) numeration systems with non-integer
alphabets are new results; in both $1$-block and $k$-block variants. Detailed
comments on these results are elaborated in Sections 7.4 and 7.5. The full
look-up tables containing the weight coefficients
$q_{j}=q_{j}(w_{j},w_{j-1},\ldots,w_{j-r+1})$, assigned to all necessary
$r$-tuples of digits $w_{j}\in\mathcal{A}+\mathcal{A}$, are published in [15].

###  7.4 Penney Numeration Systems

In 1960’s, W. Penney [18] proposed to use the complex base
$\beta_{P}=-1+\imath$ with the alphabet $\mathcal{C}_{P}=\\{0,1\\}$. Such
numeration system $(-1+\imath,\\{0,1\\})$ can represent any complex number
$X\in\mathbb{C}$ as $X=(x_{n}\ldots x_{1}x_{0}\bullet
x_{-1}\ldots)_{-1+\imath}$, with $x_{j}\in\\{0,1\\}$. The Penney base
$\beta_{P}=-1+\imath$ is an algebraic integer, with minimal polynomial
$m_{\beta_{P}}(X)=X^{2}+2X+2$. So the minimum size of alphabets
$\mathcal{A}_{P}$ allowing ($1$-block) parallel addition in base $\beta_{P}$,
according to Theorem 2.5, is limited by
$\\#\mathcal{A}_{P}\geq\max\\{|m_{\beta_{P}}(0)|,|m_{\beta_{P}-1}(0)|\\}=\max\\{2,5\\}=5\,.$
For $k$-block parallel addition, the alphabet size of $3$ is suggested in
Remark 7.1.

####  7.4.1 Penney Base with Integer Alphabet: $1$-block

We consider $5$-digit integer alphabets, e.g. non-negative
$\mathcal{A}=\\{0,\dots,4\\}$ or symmetric $\mathcal{A}=\\{-2,\dots,2\\}$. The
EWM does not work here: although Phase 1 finds successfully the weight
coefficient sets $\mathcal{Q}$, there are several digits
$b\in\mathcal{A}+\mathcal{A}$ not passing the one-letter-input part of Phase 2
in the EWM algorithm.

But we can obtain the parallel addition algorithms due to the fact that
$\beta_{P}^{4}=-4$, and using the results obtained earlier for the negative
integer base $\gamma=-4$. The modification of algorithm from base $\gamma=-4$
to $\beta_{P}=-1+\imath=\sqrt[4]{-4}$, with the same alphabet $\mathcal{A}$,
is quite simple. We perform conversion of digits from
$w_{j}\in\mathcal{A}+\mathcal{A}$ to $z_{j}\in\mathcal{A}$, by means of the
same weight coefficients $q_{j}\in\mathcal{Q}$, as follows:

$\displaystyle\mathrm{for}\ (\gamma,\mathcal{A}):$ $\displaystyle\qquad
z_{j}:=w_{j}+q_{j-1}-q_{j}\gamma=w_{j}+q_{j-1}+4q_{j}\qquad\
\mathrm{where}\quad q_{j}=q_{j}(w_{j},w_{j-1})\,;$ $\displaystyle\mathrm{for}\
(\beta_{P},\mathcal{A}):$ $\displaystyle\qquad
z_{j}:=w_{j}+q_{j-4}-q_{j}\beta_{P}^{4}=w_{j}+q_{j-4}+4q_{j}\qquad\mathrm{where}\quad
q_{j}=q_{j}(w_{j},w_{j-4})\,.$

While in $(-4,\mathcal{A})$, we had
$z_{j}=z_{j}(w_{j},q_{j},q_{j-1})=z_{j}(w_{j},w_{j-1},w_{j-2})$, and so
parallel addition was a $3$-local function, now in $(-1+\imath,\mathcal{A})$
we obtain $z_{j}=z_{j}(w_{j},q_{j},q_{j-4})=z_{j}(w_{j},w_{j-4},w_{j-8})$, and
thus $9$-local function of parallel addition, with memory $r=8$ and
anticipation $t=0$.

For the example of symmetric alphabet $\mathcal{A}=\\{0,\pm 1,\pm 2\\}$, the
weight function $q_{j}:(\mathcal{A}+\mathcal{A})^{2}\rightarrow\\{0,\pm
1\\}=\mathcal{Q}$ for parallel addition in $(\beta_{P},\mathcal{A})$ has the
following form:

$\displaystyle q_{j}=+1$ $\displaystyle\mathrm{for}$
$\displaystyle(w_{j}\leq-3)\quad\mathrm{or}\quad(w_{j}=-2\ \ \mathrm{and}\ \
w_{j-4}\geq+2)$ $\displaystyle q_{j}=-1$ $\displaystyle\mathrm{for}$
$\displaystyle(w_{j}\geq+3)\quad\mathrm{or}\quad(w_{j}=+2\ \ \mathrm{and}\ \
w_{j-4}\leq-2)$ $\displaystyle q_{j}=0\ \ $
$\displaystyle\mathrm{otherwise}\,.$

So here we have example of numeration systems $(\beta_{P},\mathcal{A})$ where
parallel addition algorithms exist, but the EWM it not able to find them,
although its prerequisites are fulfilled.

####  7.4.2 Penney Base with Complex Alphabet: $1$-block

Using the fact that $\pm\imath\equiv_{-2+\imath}\pm 2$ and the Penney base
$\beta_{P}$ fulfils $\beta_{P}-1=-2+\imath$, we can move from the integer
alphabet $\\{0,\pm 1,\pm 2\\}$ to the complex alphabet
$\mathcal{A}_{P}=\\{0,\pm 1,\pm\imath\\}$, still containing representatives of
all $5$ congruence classes modulo $\beta_{P}-1$, and, moreover,
$\mathcal{A}_{P}\cdot\mathcal{A}_{P}=\mathcal{A}_{P}$, i.e., $\mathcal{A}_{P}$
is closed under multiplication.

Application of EWM on numeration system $(-1+\imath,\\{0,\pm 1,\pm\imath\\})$
is successful – provides an algorithm of parallel addition with memory $r=6$
and anticipation $t=0$, so $7$-local function, using the weight coefficient
set of size $\\#\mathcal{Q}=45$, as follows:

$z_{j}:=w_{j}+q_{j-1}-q_{j}\beta_{P}=w_{j}+q_{j-1}-(\imath-1)q_{j}\,,$

where $q_{j}=q_{j}(w_{j},\ldots,w_{j-5})$. Hence,
$z_{j}=z_{j}(w_{j},q_{j},q_{j-1})=z_{j}(w_{j},\ldots,w_{j-6})$.

Having an alphabet $\mathcal{A}_{P}$ closed under multiplication can be
advantageous for efficiency of various arithmetic operations (e.g.
multiplication and division), but for the parallel addition itself, this
alphabet requires a very large size of the look-up table describing the weight
coefficient function $q_{j}$. The weight function has six arguments, so the
maximum size of the look-up table could be
$\\#(\mathcal{A}_{P}+\mathcal{A}_{P})^{6}=13^{6}=4\,826\,809$. The algorithm
obtained by EWM results in the look-up table for $q_{j}$ of somewhat smaller
size $2\,165\,713$ – but still, rather disadvantageous.

####  7.4.3 Penney Base with Integer Alphabet: $2$-block

The EWM algorithm is successful also in search for parallel addition algorithm
in the Penney base with an integer alphabet, using the $k$-block concept for
$k=2$. In this case, it is sufficient to take a (symmetric) alphabet of three
digits only, as suggested in Remark 7.1 for the CNS.

In the $2$-block concept, we actually regard the
$(\beta_{P},\mathcal{A}_{P_{2}})$-representation of a number $x\in\mathbb{C}$
as a (half-length) representation in a transformed numeration system
$(\widetilde{\beta_{P}},\widetilde{\mathcal{A}_{P_{2}}})$:

$\displaystyle\beta_{P}$ $\displaystyle=\imath-1$ $\displaystyle\rightarrow$
$\displaystyle\widetilde{\beta_{P}}$ $\displaystyle=\beta_{P}^{2}=-2\imath$
$\displaystyle\mathcal{A}_{P_{2}}$ $\displaystyle=\\{0,\pm 1\\}\\!\\!$
$\displaystyle\rightarrow$ $\displaystyle\widetilde{\mathcal{A}_{P_{2}}}$
$\displaystyle=\\{\beta_{P}a_{1}+a_{0}\,|\,a_{j}\in\mathcal{A}_{P_{2}}\\}=\\{(\imath-1)a_{1}+a_{0}\,|\,a_{j}\in\\{0,\pm
1\\}\\}\,,\,\\#\widetilde{\mathcal{A}_{P_{2}}}=9$ $\displaystyle x_{j}$
$\displaystyle\in\mathcal{A}_{P_{2}}$ $\displaystyle\rightarrow$
$\displaystyle x$ $\displaystyle=(x_{2n+1}x_{2n}\ldots x_{1}x_{0}\bullet
x_{-1}x_{-2}\ldots)_{\beta_{P}}=\sum_{j=-\infty}^{2n+1}x_{j}\beta_{P}^{j}$
$\displaystyle=\sum_{l=-\infty}^{n}(\beta_{P}x_{2l+1}+x_{2l})(\beta_{P}^{2})^{l}$
$\displaystyle\widetilde{x}_{l}$
$\displaystyle\in\widetilde{\mathcal{A}_{P_{2}}}$ $\displaystyle\rightarrow$
$\displaystyle x$
$\displaystyle=(\widetilde{x}_{n}\ldots\widetilde{x}_{0}\bullet\widetilde{x}_{-1}\ldots)_{\widetilde{\beta_{P}}}=\sum_{l=-\infty}^{n}\widetilde{x}_{l}(\widetilde{\beta_{P}})^{l}\quad\mathrm{with}\quad\widetilde{x}_{l}=\beta_{P}x_{2l+1}+x_{2l}\,.$

Application of the EWM algorithm on numeration system
$(\widetilde{\beta_{P}},\widetilde{\mathcal{A}_{P_{2}}})$ provides the
following result:

  * •

weight coefficient function
$\widetilde{q}:(\widetilde{\mathcal{A}_{P_{2}}}+\widetilde{\mathcal{A}_{P_{2}}})^{5}\rightarrow\widetilde{\mathcal{Q}}$,
with
$\widetilde{q}_{j}=\widetilde{q}_{j}(\widetilde{w}_{j},\ldots,\widetilde{w}_{j-4})\in\widetilde{\mathcal{Q}}\subset\mathbb{Z}[\beta]$,
described by $60\,721$ distinct input combinations
$(\widetilde{w}_{j},\ldots,\widetilde{w}_{j-4})$;

  * •

parallel addition
$\widetilde{z}_{j}:=\widetilde{w}_{j}+\widetilde{q}_{j-1}-\widetilde{q}_{j}\widetilde{\beta_{P}}$
is then a $6$-local function, with memory $r=5$ and anticipation $t=0$, with
respect to the numeration system
$(\widetilde{\beta_{P}},\widetilde{\mathcal{A}_{P_{2}}})$;

  * •

this means, in view of the original numeration system
$(\beta_{P},\mathcal{A}_{P_{2}})$, a $12$-local function, with parameters of
memory and anticipation equal to $r=10$, $t=1$ for even positions, and $r=11$,
$t=0$ for odd positions.

So the alphabet $\mathcal{A}_{P_{2}}$ for $2$-block parallel addition could be
limited to just three elements $\\{0,\pm 1\\}$, and also the look-up table (of
$60\,721$ items) describing the weight coefficient function is smaller than in
the $1$-block case. Similar results as on the symmetric alphabet
$\mathcal{A}_{P_{2}}=\\{-1,0,1\\}$ are obtained by EWM also for the non-
negative alphabet $\mathcal{A}_{P_{2}}=\\{0,1,2\\}$; the latter result has the
same $p$-locality, but larger look-up table describing the weight coefficient
function on $114\,481$ distinct input combinations
$(\widetilde{w}_{j},\ldots,\widetilde{w}_{j-4})$.

####  7.4.4 Penney Base with Complex Alphabet: $2$-block

Attempts to apply the EWM method on non-integer alphabets $\mathcal{A}$ of
size $3$, containing $\\{0,1\\}$, were not successful with the $2$-block
approach. As the third element of the alphabet $\mathcal{A}$, all of the five
remaining elements of $\mathbb{Z}[\beta]$ on the unit circle were tried:
$-1,\pm\imath,\imath$; but they all have failed, in various steps of the EWM
algorithm.

###  7.5 Eisenstein Numeration Systems

Let us denote by $\omega$ the third root of unity
$\omega=\exp{\tfrac{2\pi\imath}{3}}=\tfrac{-1+\imath\sqrt{3}}{2}$, an
algebraic integer with minimal polynomial $m_{\omega}(X)=X^{2}+X+1$.
Eisenstein base is the complex number
$\beta_{E}=-1+\omega=\tfrac{-3+\imath\sqrt{3}}{2}$, an algebraic integer with
minimal polynomial $m_{\beta_{E}}(X)=X^{2}+3X+3$. This number $\beta_{E}$
generates the set $\mathbb{Z}[\beta_{E}]$ of so-called _Eisenstein integers_
of the form:

$\mathbb{Z}[\beta_{E}]=\left\\{\left.\sum_{k=0}^{n}a_{k}\beta_{E}^{k}\,\right|\,n\in\mathbb{Z}^{+},a_{k}\in\mathbb{Z}\right\\}=\left\\{a_{1}\beta_{E}+a_{0}\,|\,a_{k}\in\mathbb{Z}\right\\}\quad\mathrm{with}\quad\beta_{E}=\tfrac{-3+\imath\sqrt{3}}{2}\,.$
(11)

Again, we derive the minimum size of alphabets $\mathcal{A}_{E}$ (integer or
complex) allowing $1$-block parallel addition in this base, due to Theorem
2.5, as
$\\#\mathcal{A}_{E}\geq\max\\{|m_{\beta_{E}}(0)|,|m_{\beta_{E}-1}(0)|\\}=\max\\{3,7\\}=7\,.$
For $k$-block parallel addition, the alphabet size of $5$ is suggested in
Remark 7.1.

####  7.5.1 Eisenstein Base with Integer Alphabet: $1$-block

We consider $7$-digit integer alphabets, non-negative
$\mathcal{A}=\\{0,\ldots,6\\}$ or symmetric $\mathcal{A}=\\{-3,\ldots,3\\}$,
and apply the EWM on such numeration systems – but unsuccessfully. Phase 1
does find the weight coefficient sets $\mathcal{Q}$, but there are several
digits $b\in\mathcal{A}+\mathcal{A}$ not passing the one-letter-input part of
Phase 2 in the EWM.

Parallel addition algorithms for the Eisenstein base $\beta_{E}$ with the
mentioned integer alphabets $\mathcal{A}$ could be found manually, using the
rewriting rule $X^{2}+3X+3$, but with quite complex weight function; and the
resulting parallel addition function would be $9$-local.

####  7.5.2 Eisenstein Base with Complex Alphabet: $1$-block

We have applied the EWM successfully on the following alphabet
$\mathcal{A}_{E}\subset\mathbb{Z}[\beta_{E}]$ of the minimal size:

$\mathcal{A}_{E}=\\{0,\pm 1,\pm\omega,\pm\omega^{2}\\}=\\{0,\pm
1,\pm\omega,\pm(\omega+1)\\}\qquad\text{with}\qquad\\#\mathcal{A}_{E}=7\,.$
(12)

This alphabet $\mathcal{A}_{E}$ is non-integer, but it has many advantages:
besides fitting into the minimal $7$-digit size for parallel addition, it is
centrally symmetric ($-\mathcal{A}_{E}=\mathcal{A}_{E}$), and also closed
under multiplication ($\mathcal{A}_{E}\cdot\mathcal{A}_{E}=\mathcal{A}_{E}$).

The EWM provides parallel addition algorithm in numeration system
$(\beta_{E},\mathcal{A}_{E})$, as follows:

  * •

the weight coefficients set is, by coincidence, equal to
$\mathcal{Q}_{E}=\mathcal{A}_{E}+\mathcal{A}_{E}$ of size
$\\#\mathcal{Q}_{E}=19$;

  * •

the memory parameter $r=3$, i.e., each weight coefficient
$q_{j}\in\mathcal{Q}_{E}$ depends on (at most) $3$ digits of the
representation of $w=w_{n}\ldots
w_{1}w_{0}\raisebox{0.43057pt}{{.}}w_{-1}\ldots
w_{-m}\in(\mathcal{A}_{E}+\mathcal{A}_{E})^{*}$:

$q_{j}=q_{j}(w_{j},w_{j-1},w_{j-2})\in\mathcal{Q}_{E}\qquad\text{such \
that}\qquad z_{j}=w_{j}+q_{j-1}-q_{j}\beta_{E}\in\mathcal{A}_{E}\,;$

  * •

thus $p=r+1=4$, i.e., the parallel addition is a $4$-local function:

$z_{j}=z_{j}(w_{j},q_{j-1}(w_{j-1},w_{j-2},w_{j-3}),q_{j}(w_{j},w_{j-1},w_{j-2}))=z_{j}(w_{j},\ldots,w_{j-3})\in\mathcal{A}_{E}\,.$

The memory $r=3$ means that description of the weight coefficient function
$q_{j}:(\mathcal{A}_{E}+\mathcal{A}_{E})^{3}\rightarrow\mathcal{Q}_{E}$
requires to provide the values $q_{j}=q_{j}(w_{j},w_{j-1},w_{j-2})$ for up to
$19^{3}=6\,859$ combinations of triplets
$(w_{j},w_{j-1},w_{j-2})\in(\mathcal{A}_{E}+\mathcal{A}_{E})^{3}$. This look-
up table can be economized by making use of the $6$-fold rotation symmetry of
the sets $\mathcal{A}_{E}$, $\mathcal{A}_{E}+\mathcal{A}_{E}$,
$\mathcal{Q}_{E}$. Let us denote:

$\mathcal{R}:=\left\\{\left.\pm\omega^{k}\,\right|\,k\in\mathbb{Z}\right\\}=\left\\{\pm
1,\pm\omega,\pm\omega^{2}\right\\}\,.$

Then, for any element $\rho\in\mathcal{R}$, we have
$\rho\mathcal{A}_{E}=\mathcal{A}_{E}$,
$\rho(\mathcal{A}_{E}+\mathcal{A}_{E})=(\mathcal{A}_{E}+\mathcal{A}_{E})$,
$\rho\mathcal{Q}_{E}=\mathcal{Q}_{E}$, and, consequently, for any set of
digits $w_{j},w_{j-1},w_{j-2},w_{j-3}\in\mathcal{A}_{E}+\mathcal{A}_{E}$:

$\displaystyle q_{j}(\rho w_{j},\rho w_{j-1},\rho w_{j-2})$
$\displaystyle=\rho q_{j}(w_{j},w_{j-1},w_{j-2})\,,$ $\displaystyle z_{j}(\rho
w_{j},\rho w_{j-1},\rho w_{j-2},\rho w_{j-3})$ $\displaystyle=\rho
w_{j}+q_{j-1}(\rho w_{j-1},\rho w_{j-2},\rho w_{j-3})-q_{j}(\rho w_{j},\rho
w_{j-1},\rho w_{j-2})\beta_{E}$ $\displaystyle=\rho w_{j}+\rho
q_{j-1}(w_{j-1},w_{j-2},w_{j-3})-\rho q_{j}(w_{j},w_{j-1},w_{j-2})\beta_{E}$
(13)
$\displaystyle=\rho(w_{j}+q_{j-1}(w_{j-1},w_{j-2},w_{j-3})-q_{j}(w_{j},w_{j-1},w_{j-2})\beta_{E})$
$\displaystyle=\rho z_{j}(w_{j},w_{j-1},w_{j-2},w_{j-3})\,.$

Figure 1: To describe the algorithm of parallel addition in the complex
Eisenstein numeration system $(\beta_{E},\mathcal{A}_{E})$, it is sufficient
to provide the weight coefficients $q_{j}=q_{j}(w_{j},w_{j-1},w_{j-2})$ for
just those triplets
$(w_{j},w_{j-1},w_{j-2})\in(\mathcal{A}_{E}+\mathcal{A}_{E})^{3}$ starting
with $w_{j}\in\\{0,1,2,1-\omega^{2}\\}$. The remaining weight coefficients are
then obtained by using the equation (7.5.2) for all $\rho\in\mathcal{R}$.

####  7.5.3 Eisenstein Base with Integer Alphabet: $3$-block

With help of the EWM, we find out that the $k$-block concept with $k=3$ helps
to decrease the alphabet size for parallel addition in Eisenstein base with
integer alphabets, from $\mathcal{A}_{E}=7$ down to $\mathcal{A}_{E_{3}}=5$.
This result is obtained for the symmetric case
$\mathcal{A}_{E_{3}}=\\{-2,\ldots,2\\}$ as well as for the non-negative case
$\mathcal{A}_{E_{3}}=\\{0,\ldots,4\\}$.

####  7.5.4 Eisenstein Base with Complex Alphabet: $3$-block

In the tested cases below, the alphabets $\mathcal{A}$ are selected as subsets
of $\\{0,\pm 1,\pm\omega,\pm\omega^{2}\\}$.

  * •

$2$-block function on $4$-digit alphabets: All cases pass successfully via
Phase 1, but then fail in Phase 2. There are always (quite many) elements
$b\in\widetilde{\mathcal{A}}_{E}+\widetilde{\mathcal{A}}_{E}$ which do no pass
the $\mathcal{Q}[b^{m}]$-test.

  * •

$3$-block function on $4$-digit alphabets: All cases fail already in Phase 1;
due to the fact that (quite many) representatives of the congruence classes
$\mod(\widetilde{\beta}-1)$ are missing in the alphabet
$\widetilde{\mathcal{A}}_{E}$.

  * •

$2$-block function on $5$-digit alphabets: All cases pass successfully via
Phase 1, but then fail in Phase 2. Already the $\mathcal{Q}[b^{m}]$-test of
Phase 2 is never passed successfully, although in some cases for one element
$b\in\widetilde{\mathcal{A}}_{E}+\widetilde{\mathcal{A}}_{E}$ only.

  * •

$3$-block function on $5$-digit alphabets: Here we obtain a successful result.
There are 15 possible combinations of 5-digit subsets in $\mathcal{A}_{E}$
(containing $0$), and for 9 of them (depicted on Figure 2), parallel addition
can be performed via a 3-block $p$-local function. The memory parameter $r$
ranges from 2 to 4; and, with the shortest possible memory $r=2$, we have:

    * –

$p=r+1=3$, and thus a $3$-block $3$-local addition function
$\varphi:(\mathcal{A}_{E3}+\mathcal{A}_{E3})^{9}\rightarrow\mathcal{A}_{E3}$;

    * –

using one of two alphabets
$\pm\mathcal{A}_{E3}=\pm\\{0,1,\omega,-\omega,-\omega^{2}\\}$;

    * –

with the $3$-block set
$\widetilde{\mathcal{A}_{E3}}=\\{a_{2}\beta^{2}+a_{1}\beta+a_{0}\,|\,a_{j}\in\mathcal{A}_{E3}\\}$
of size $\\#\widetilde{\mathcal{A}_{E3}}=72$;

    * –

base $\beta_{E3}=\beta_{E}^{3}=(\omega-1)^{3}=6\omega+3$;

    * –

weight coefficients set equal to (or a subset of)
$\mathcal{Q}_{E}=\mathcal{A}_{E}+\mathcal{A}_{E}$ of size $\\#\mathcal{Q}=19$;

    * –

and the input alphabet $\mathcal{A}_{E3}+\mathcal{A}_{E3}$ of size
$\\#(\mathcal{A}_{E3}+\mathcal{A}_{E3})=280$.

A full description of the weight coefficient function would comprise
$(\\#(\mathcal{A}_{E3}+\mathcal{A}_{E3}))^{r}=280^{2}=78\,400$ values. This
maximum number is diminished to $161+33\,320=161+119*280$, since for $161$
input digits, the weight coefficient depends on just one position
($q_{j}=q_{j}(w_{j})$), and only for the remaining $119$ input digits, we have
to consider also their neighbour to the right ($q_{j}=q_{j}(w_{j},w_{j-1})$).

Figure 2: Here we depict the 9 subsets with 5 digits (including $0$) in
$\mathcal{A}_{E}$, allowing parallel addition via a 3-block local function.
Variants no. 1. and 4. have the minimal memory $r=2$ of the parallel addition
function.

##  8 Conclusions

The (automated) Extending Window Method (EWM) for construction of parallel
addition algorithms, as proposed and elaborated in this work, can be regarded
in fact as generalization of the intuitive (manual) methods used by other
authors earlier. For instance, the EWM delivers the same parallel addition
algorithms for integer bases as found previously by [1], [2], [17], or [5], as
illustrated in Table 1.

When considering certain classes of real or complex bases (quadratic, or
$\ell$-th roots of integers), the EWM does provide parallel addition
algorithms on (integer or non-integer) alphabets of minimal size, however,
some of the underlying local functions are rather complex, even more than in
some of the algorithms found manually earlier. See selected examples of real
bases in Tables 2 and 3, and of complex bases in Tables 4 and 5.

In the case of complex bases and non-integer alphabets, manual search for the
parallel addition algorithms is extremely laborious (if possible at all); but
the EWM could do that successfully (including block parallel addition as
well), e.g. for the Penney and Eisenstein bases, samples of the Canonical
Numeration Systems, as summarized in Table 6.

Open problems remaining for future analysis regarding the Extending Window
Method for construction of parallel addition algorithms are mainly the
following:

  * •

Generalization of the Extending Window Method implementation using an
arbitrary rewriting rule, instead of just $(X-\beta)$. This may be useful
especially for numeration systems $(\beta,\mathcal{A})$ with non-integer base
$\beta\in\mathbb{C}\setminus\mathbb{Z}$ and integer alphabet
$\mathcal{A}\subset\mathbb{Z}$.

  * •

Answering the open question of Phase 2 convergence within the Extending Window
Method. This would require deeper analysis of underlying mathematical
structures for the various methods considered to select the weight
coefficients while iterating within Phase 2.

## Acknowledgements

The authors acknowledge financial support from the Czech Science Foundation
(grant GAČR 13-03538S) and from the Czech Technical University in Prague
(grant SGS 17/193/OHK4/3T/14).

## References

  * [1] A. Avizienis.  Signed-Digit Number Representations for Fast Parallel Arithmetic.  IEEE Trans. Comput., 10:389–400, 1961.
  * [2] C.Y. Chow and J.E. Robertson.  Logical design of a redundant binary adder.  Proc. IEEE 4th Symp. on Comp. Arith., pages 109–115, 1978.
  * [3] C. Frougny, P. Heller, E. Pelantová, and M. Svobodová.  k-Block parallel addition versus 1-block parallel addition in non-standard numeration systems.  Theoret. Comput. Sci., 543:52–67, 2014.
  * [4] C. Frougny, E. Pelantová, and M. Svobodová.  Parallel addition in non-standard numeration systems.  Theoret. Comput. Sci., 412:5714–5727, 2011.
  * [5] C. Frougny, E. Pelantová, and M. Svobodová.  Minimal digit sets for parallel addition in non-standard numeration systems.  J. Integer Seq., 16:36, 2013.
  * [6] Y. Herreros.  Contribution à l’arithmétique des ordinateurs.  Ph.d. dissertation, Institut National Polytechnique de Grenoble, 1991\.
  * [7] R. A. Horn and C. R. Johnson.  Matrix Analysis.  Cambridge University Press, 1990.
  * [8] P. Kornerup.  Necessary and Sufficient Conditions for Parallel, Constant Time Conversion and Addition.  Proc. 14th IEEE Symp. on Comp. Arith., pages 152–155, 1999.
  * [9] B. Kovács.  Canonical number systems in algebraic number fields.  Acta Math. Hung., 37(4):405–407, 1981.
  * [10] B. Kovács and A. Pethö.  Number systems in integral domains, especially in orders of algebraic number fields.  Acta Sci. Math. (Szeged), 55:287–299, 1991.
  * [11] I. Kátai.  Generalized number systems in Euclidean spaces.  Math. Comput. Model., 38:883–892, 2003.
  * [12] J. Legerský.  Construction of algorithms for parallel addition in non-standard numeration systems.  Master thesis, Czech Technical University in Prague, FNSPE, Czech Republic, 2016.  http://jan.legersky.cz/pdf/master_thesis_parallel_addition.pdf.
  * [13] J. Legerský.  Construction of Parallel Addition Algorithms by the Extending Window Method – implementation.  Zenodo, 2018.  https://doi.org/10.5281/zenodo.1542942.
  * [14] J. Legerský.  Minimal non-integer alphabets allowing parallel addition.  Acta Polytech., 58(5):285–291, 2018.
  * [15] J. Legerský and M. Svobodová.  Construction of Parallel Addition Algorithms by the Extending Window Method – results.  Zenodo, 2018.  https://doi.org/10.5281/zenodo.1541074.
  * [16] A.M. Nielsen and J.-M. Muller.  Borrow-save adders for real and complex number systems.  Proc. Real Numbers and Computers, pages 121–137, 1996.
  * [17] B. Parhami.  On the implementation of arithmetic support functions for generalized signed-digit number systems.  IEEE Trans. Computers, 42:379–384, 1993.
  * [18] W. Penney.  A ’binary’ system for complex numbers.  J. Assoc. Computing Machinery, 12:247–248, 1965.