Journal of Integer Sequences, Vol. 16 (2013), Article 13.2.17

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