Source author record

Milena Svobodová

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.NT Discrete Mathematics

Catalog footprint

Research overview

2works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

$k$ -block parallel addition versus $1$ -block parallel addition in non-standard numeration systems

Parallel addition in integer base is used for speeding up multiplication and division algorithms. $k$ -block parallel addition has been introduced by Kornerup in 1999: instead of manipulating single digits, one works with blocks of fixed length $k$ . The aim of this paper is to investigate how such notion influences the relationship between the base and the cardinality of the alphabet allowing parallel addition. In this paper, we mainly focus on a certain class of real bases --- the so-called Parry numbers. We give lower bounds on the cardinality of alphabets of non-negative integer digits allowing block parallel addition. By considering quadratic Pisot bases, we are able to show that these bounds cannot be improved in general and we give explicit parallel algorithms for addition in these cases. We also consider the $d$ -bonacci base, which satisfies the equation $X^d = X^{d-1} + X^{d-2} + \cdots + X + 1$ . If in a base being a $d$ -bonacci number $1$ -block parallel addition is possible on the alphabet $\mathcal{A}$ , then $\#\mathcal{A} \geq d+1$ ; on the other hand, there exists a $k\in\mathbb{N}$ such that $k$ -block parallel addition in this base is possible on the alphabet $\{0,1,2\}$ , which cannot be reduced. In particular, addition in the Tribonacci base is $14$ -block parallel on alphabet $\{0,1,2\}$ .

preprint2011arXiv

Parallel addition in non-standard numeration systems

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Milena Svobodová

Research overview

Is this your work?

2 publications

$k$ -block parallel addition versus $1$ -block parallel addition in non-standard numeration systems

Parallel addition in non-standard numeration systems

See the researcher in context

Building this map preview

Milena Svobodová

Research overview

Is this your work?

2 publications

kkk-block parallel addition versus 111-block parallel addition in non-standard numeration systems

Parallel addition in non-standard numeration systems

See the researcher in context

Building this map preview

$k$ -block parallel addition versus $1$ -block parallel addition in non-standard numeration systems