##
**
Minimal Digit Sets for Parallel Addition in Non-Standard Numeration Systems
**

###
Christiane Frougny

LIAFA, CNRS UMR 7089

Case 7014

75205 Paris Cedex 13

France

Edita Pelantová and Milena Svobodová

Doppler Institute for Mathematical Physics and Applied Mathematics, and Department
of Mathematics

Czech Technical University in Prague

Trojanova 13

120 00 Praha 2

Czech Republic

**Abstract:**

We study parallel algorithms for addition of numbers having finite
representation in a positional numeration system defined by a base
β in **C** and a finite digit set *A* of
contiguous integers containing 0. For a fixed base β, we
focus on the question of the size of the alphabet that permits
addition in constant time, independently of the length of
representation of the summands. We produce lower bounds on the
size of such alphabet *A*. For several types of well-studied bas
es (negative integer, complex numbers -1 + i,
2i , and i√2, quadratic Pisot units, and
non-integer rational bases), we give explicit parallel algorithms
performing addition in constant time. Moreover we show that digit
sets used by these algorithms are the smallest possible.

**
Full version: pdf,
dvi,
ps,
latex
**

(Concerned with sequence
A000108.)

Received August 4 2012;
revised version received February 10 2013.
Published in *Journal of Integer Sequences*, March 2 2013.

Return to
**Journal of Integer Sequences home page**