Construction of algorithms for parallel addition in expanding bases via Extending Window Method

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21340%2F19%3A00326521" target="_blank" >RIV/68407700:21340/19:00326521 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.tcs.2019.08.010" target="_blank" >https://doi.org/10.1016/j.tcs.2019.08.010</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Construction of algorithms for parallel addition in expanding bases via Extending Window Method

Popis výsledku v původním jazyce

An algebraic number βelementC without conjugates of modulus 1 can serve as the base of a numeration system (β,A) allowing parallel addition, i.e., the sum of two operands represented in β with digits from A is calculated in constant time, irrespective of the length of the operands. To allow parallel addition, sufficient redundancy must exist in the alphabet A. The complexity of parallel addition algorithms depends heavily on the alphabet size: smaller alphabet implies higher complexity of the algorithm. We search for parallel addition algorithms on alphabets of the minimum possible size for a given base. To handle high complexity of these algorithms, we introduce a so-called Extending Window Method (EWM) – an algorithm constructing parallel addition algorithms. It can be applied on bases being expanding algebraic integers, with all conjugates > 1 in modulus. The convergence of the EWM is not guaranteed. Nevertheless, we developed tools for revealing non-convergence, and found some successful applications. The EWM provides equal parallel addition algorithms as introduced earlier by A. Avizienis, C.Y. Chow & J.E. Robertson or B. Parhami for integer bases and alphabets. Applying the EWM on complexbases β with non-integer alphabets AcZ[β] delivers new results, not found previously.

Název v anglickém jazyce

Construction of algorithms for parallel addition in expanding bases via Extending Window Method

Popis výsledku anglicky

An algebraic number βelementC without conjugates of modulus 1 can serve as the base of a numeration system (β,A) allowing parallel addition, i.e., the sum of two operands represented in β with digits from A is calculated in constant time, irrespective of the length of the operands. To allow parallel addition, sufficient redundancy must exist in the alphabet A. The complexity of parallel addition algorithms depends heavily on the alphabet size: smaller alphabet implies higher complexity of the algorithm. We search for parallel addition algorithms on alphabets of the minimum possible size for a given base. To handle high complexity of these algorithms, we introduce a so-called Extending Window Method (EWM) – an algorithm constructing parallel addition algorithms. It can be applied on bases being expanding algebraic integers, with all conjugates > 1 in modulus. The convergence of the EWM is not guaranteed. Nevertheless, we developed tools for revealing non-convergence, and found some successful applications. The EWM provides equal parallel addition algorithms as introduced earlier by A. Avizienis, C.Y. Chow & J.E. Robertson or B. Parhami for integer bases and alphabets. Applying the EWM on complexbases β with non-integer alphabets AcZ[β] delivers new results, not found previously.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2019

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

1879-2294

Svazek periodika

795

Číslo periodika v rámci svazku

November

Stát vydavatele periodika

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

Počet stran výsledku

23

Strana od-do

547-569

Kód UT WoS článku

000494887800042

EID výsledku v databázi Scopus

2-s2.0-85071323326