On-line algorithms for multiplication and division in real and complex numeration systems

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="https://doi.org/10.23638/DMTCS-21-3-14" target="_blank" >https://doi.org/10.23638/DMTCS-21-3-14</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.23638/DMTCS-21-3-14" target="_blank" >10.23638/DMTCS-21-3-14</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On-line algorithms for multiplication and division in real and complex numeration systems

Popis výsledku v původním jazyce

A positional numeration system is given by a base and by a set of digits. The base is a real or complex number β such that |β|>1, and the digit set A is a finite set of digits including 0. Thus a number can be seen as a finite or infinite string of digits. An on-line algorithm processes the input piece-by-piece in a serial fashion. On-line arithmetic, introduced by Trivedi and Ercegovac, is a mode of computation where operands and results flow through arithmetic units in a digit serial manner, starting with the most significant digit. In this paper, we first formulate a generalized version of the on-line algorithms for multiplication and division of Trivedi and Ercegovac for the cases that β is any real or complex number, and digits are real or complex. We then define the so-called OL Property, and show that if (β,A) has the OL Property, then on-line multiplication and division are feasible by the Trivedi-Ercegovac algorithms. For a real base β and a digit set A of contiguous integers, the system (β,A) has the OL Property if #A>|β|. For a complex base β and symmetric digit set A of contiguous integers, the system (β,A) has the OL Property if #A>ββ+|β+β|. Provided that addition and subtraction are realizable in parallel in the system (β,A) and that preprocessing of the denominator is possible, our on-line algorithms for multiplication and division have linear time complexity. Three examples are presented in detail: base β=3+5root 2 with digits A={-1,0,1}; base β=2i with digits A={-2,-1,0,1,2}; and base β=-32+i3root 2=-1+ω, where ω=exp2iπ3, with digits A={0,±1,±ω,±ω2}.

Název v anglickém jazyce

On-line algorithms for multiplication and division in real and complex numeration systems

Popis výsledku anglicky

A positional numeration system is given by a base and by a set of digits. The base is a real or complex number β such that |β|>1, and the digit set A is a finite set of digits including 0. Thus a number can be seen as a finite or infinite string of digits. An on-line algorithm processes the input piece-by-piece in a serial fashion. On-line arithmetic, introduced by Trivedi and Ercegovac, is a mode of computation where operands and results flow through arithmetic units in a digit serial manner, starting with the most significant digit. In this paper, we first formulate a generalized version of the on-line algorithms for multiplication and division of Trivedi and Ercegovac for the cases that β is any real or complex number, and digits are real or complex. We then define the so-called OL Property, and show that if (β,A) has the OL Property, then on-line multiplication and division are feasible by the Trivedi-Ercegovac algorithms. For a real base β and a digit set A of contiguous integers, the system (β,A) has the OL Property if #A>|β|. For a complex base β and symmetric digit set A of contiguous integers, the system (β,A) has the OL Property if #A>ββ+|β+β|. Provided that addition and subtraction are realizable in parallel in the system (β,A) and that preprocessing of the denominator is possible, our on-line algorithms for multiplication and division have linear time complexity. Three examples are presented in detail: base β=3+5root 2 with digits A={-1,0,1}; base β=2i with digits A={-2,-1,0,1,2}; and base β=-32+i3root 2=-1+ω, where ω=exp2iπ3, with digits A={0,±1,±ω,±ω2}.

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

Discrete Mathematics and Theoretical Computer Science

ISSN

1462-7264

e-ISSN

1365-8050

Svazek periodika

21

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

FR - Francouzská republika

Počet stran výsledku

26

Strana od-do

—

Kód UT WoS článku

000480436900001

EID výsledku v databázi Scopus

—