Parallel addition in non-standard numeration systems

Details Parallel addition in non-standard numeration systems Parallel addition in non-standard numeration systems

2011-02-28

arxiv.org/abs/1102.5683v2

Mathematics

Number Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Parallel addition in non-standard numeration systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Parallel addition in non-standard numeration systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel addition in non-standard numeration systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-425556