arXiv (Cornell University) · 2016 · 13 citations · 19 references
ComputingComputer ScienceMathematicsAlgorithmsNumber TheoryParallel AlgorithmsCombinatorial Number TheoryComputational Number TheoryData ParallelismNumber-theoretic AlgorithmsParallel ArchitecturesParallel Data StructuresConstant-time AlgorithmsLower BoundsMinimal Sets
We study parallel algorithms for addition of numbers having finite representation in a positional numeration system defined by a base $β$ in $\mathbb{C}$ and a finite digit set $\mathcal{A}$ of contiguous integers containing $0$. For a fixed base $β$, we focus on the question of the size of the alphabet allowing to perform addition in constant time independently of the length of representation of the summands. We produce lower bounds on the size of such alphabet $\mathcal{A}$. For several types of well studied bases (negative integer, complex numbers $ -1 + \imath$, $2 \imath$, and $\imath \sqrt{2}$, quadratic Pisot unit, and the non-integer rational base), we give explicit parallel algorithms performing addition in constant time. Moreover we show that digit sets used by these algorithms are the smallest possible.
19
On theβ-expansions of real numbers
William Parry · Acta Mathematica Academiae Scientiarum Hungaricae · 1960 · 846 citations
Unique expansions of real numbers
Martijn de Vries, Vilmos Komornik · Advances in Mathematics · 2009 · 164 citations