Parallel addition in non-standard numeration systems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21340%2F11%3A00187206" target="_blank" >RIV/68407700:21340/11:00187206 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.tcs.2011.06.028" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2011.06.028</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2011.06.028" target="_blank" >10.1016/j.tcs.2011.06.028</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Parallel addition in non-standard numeration systems

Popis výsledku v původním jazyce

We consider numeration systems where digits are integers and the base is an algebraic number $beta$ such that $|beta|>1$ and $beta$ satisfies a polynomial where one coefficient is dominant in a certain sense. For this class of bases $beta$, 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 $beta$ satisfies this dominance condition if and only if it has no conjugate of modulus $1$. When the base $beta$ 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.

Název v anglickém jazyce

Parallel addition in non-standard numeration systems

Popis výsledku anglicky

We consider numeration systems where digits are integers and the base is an algebraic number $beta$ such that $|beta|>1$ and $beta$ satisfies a polynomial where one coefficient is dominant in a certain sense. For this class of bases $beta$, 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 $beta$ satisfies this dominance condition if and only if it has no conjugate of modulus $1$. When the base $beta$ 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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F09%2F0584" target="_blank" >GA201/09/0584: Algebraické a kombinatorické aspekty aperiodických struktur</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2011

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

412

Číslo periodika v rámci svazku

41

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

14

Strana od-do

5714-5727

Kód UT WoS článku

000295498100007

EID výsledku v databázi Scopus

—