Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Let two numbers $x,y$ be represented in some digit form (binary, octal, ...): $(x_1 x_2 x_3 \ldots)$ and $(y_1 y_2 y_3 \ldots)$.

Can we add those numbers such that we do not need to carry over: $x_i = x_i+y_i + c(x_{i-1},y_{i-1})$ where $c(x_{i-1},y_{i-1})$ is the carry value of $x_{i-1}$ and $y_{i-1}$.

Are there $O(1)$ step circuit implementations of addition that exist? Are they practical?

In other words, is addition inherently recursive over the number of digits?

share|improve this question

2 Answers 2

For non-redundant representations like $(x_n, x_{n-1}, ..., {x_1})$ the recursion is fundamental (although the operator is associative so you can apply the prefix sum optimization to parallelize the operation down to $O(\lg n)$ steps.)

But there are redundant representations where addition can be performed more efficiently, in some cases. The carry-save adder is used in most hardware multiplier implementations, where you need to sum together a large list of numbers.

The redundant representation is just to represent every number by two subsums:

c3 c2 c1
x3 x2 x1 x0

so, for example, the number "5" can be stored either as:

 0  0  0
 0  1  0  1

or

 0  0  1
 0  0  1  1

The "addition" operation adds three subsums and produces two subsums:

 0  0  1
+0  0  1  1
+0  0  0  1
-----------
 0  1  1  0
 0  0  0  0

So, not very useful if you are just adding two numbers, but when you need to sum a whole list of numbers, each individual addition is fast, and then only at the end do you have to convert back to a non-redundant representation.

There are other redundant representations used in hardware multiplication algorithms, like Booth encoding where the digits can be positive, zero or negative.

share|improve this answer

For every length of x you can create an adder that will calculate the addition in "one step", actually two (and+or) in BNF, but if you have larger numbers combined of several x you will need to carry over the result for each step.

Interesting are maybe analogous adders, where you convert your number to voltages, add those and convert the result back and also those (don't remember the name) where every digit of the number counts as 1 and you adding two numbers, e.g. 3+4 = 111+1111 gives you 1111111 = 7,

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.