
arXiv: 1102.5683
We consider numeration systems where digits are integers and the base is an algebraic number $β$ such that $|β|>1$ and $β$ satisfies a polynomial where one coefficient is dominant in a certain sense. For this class of bases $β$, we can find an alphabet of signed-digits on which addition is realizable by a parallel algorithm in constant time. This algorithm is a kind of generalization of the one of Avizienis. We also discuss the question of cardinality of the used alphabet, and we are able to modify our algorithm in order to work with a smaller alphabet. We then prove that $β$ satisfies this dominance condition if and only if it has no conjugate of modulus 1. When the base $β$ is the Golden Mean, we further refine the construction to obtain a parallel algorithm on the alphabet $\{-1,0,1\}$. This alphabet cannot be reduced any more.
FOS: Computer and information sciences, Mathematics - Number Theory, Discrete Mathematics (cs.DM), Numeration, Addition, Formal languages and automata, Symbolic computation and algebraic computation, Theoretical Computer Science, Parallel algorithm, Golden Mean, addition, parallel algorithm, golden mean, numeration, FOS: Mathematics, Number Theory (math.NT), Parallel algorithms in computer science, Computer Science(all), Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Mathematics - Number Theory, Discrete Mathematics (cs.DM), Numeration, Addition, Formal languages and automata, Symbolic computation and algebraic computation, Theoretical Computer Science, Parallel algorithm, Golden Mean, addition, parallel algorithm, golden mean, numeration, FOS: Mathematics, Number Theory (math.NT), Parallel algorithms in computer science, Computer Science(all), Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 18 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
