Combinatorical and Algebraic Structures Seminar
Session details
Date: | 9.11.2010 |
Speaker: | Milena Svobodová, |
Title: | Parallel addition in non-standard numeration systems |
Abstract: | (spoluautoři: C. Frougny and E. Pelantová) We consider numeration systems where the base is an algebraic number $\beta$ such that $|\beta|>1$ and the digits are integers. When $\beta$ is a root of a polynomial with a dominant coefficient, 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 by Avizienis. We give a method to find such polynomial from the minimal one of $\beta$. In the case where the base is the Golden Mean, we refine the construction to obtain a parallel algorithm on the alphabet $\{-1,0, 1\}$. |
Slides: | 20101109.pdf |
Return to index.
last update: 27.9.2007, webmaster: Petr Ambrož