Is there any algebraic representation of natural numbers admitting parallel addition?

Question

Natural numbers can be represented in a logarithmic space using a binary representation (here in little-endian):

-- The type of binary numbers; little-endian; O = Zero, I = One data Bin = O Bin | I Bin | End 

Adding a and b can be implemented, for example, by calling the function successor ( O(log(N)) ) a times on b . The problem with this implementation is that it is inherently consistent. To add 2 numbers, suc calls alternate sequentially. Other add implementations (e.g. using a carry) suffer from the same problem. It is easy to see that the add-on cannot be implemented in parallel with this view. Is there any representation of natural numbers using algebraic data types that take a logarithmic space and that can be parallelized?

Code for illustration:

 -- The usual fold fold :: Bin -> (t -> t) -> (t -> t) -> t -> t fold (O bin) zero one end = zero (fold bin zero one end) fold (I bin) zero one end = one (fold bin zero one end) fold E zero one end = end -- Successor of `Bin` - `O(log(N))` suc :: Bin -> Bin suc (O bin) = I bin suc (I bin) = O (suc bin) suc E = E -- Calls a function `a` times times :: Bin -> (t -> t) -> t -> t times afx = fold a zero one end f where one bin fs = fs (bin (fs . fs)) zero bin fs = bin (fs . fs) end fs = x -- Adds 2 binary numbers add :: Bin -> Bin -> Bin add ab = (a `times` suc) b -- 1001 + 1000 = 0101 main = print $ add (I (O (O (IE)))) (I (O (O (OE)))) 

Answer 1

There are many parallel algorithms. An excellent review is given at Thomas Walker Lynch, thesis at the University of Texas at Austin, 1996 . See Section 9.1 for a summary of the worst-case path lengths.

The adder Lynch and Swartzlander (L & S) has the worst path length of 2 * ceil (log4 (N)) + 2, where N is the number of bits. The architecture is presented in their article, Spanning Tree Carry Lookahead Adder .

You can find great explanations on many simple architectures with googling "fast adder".

Answer 2

You did not say that every natural number must have a unique representation. So here is another option. (I did not invent it, but I don’t remember what it is called, so I had to reconstruct how it works.)

Represent numbers as strings of numbers in base 2 as in binary format, except that instead of being limited to the numbers 0 and 1, we are additionally allowed to use the number 2. So, for example, number 2 has two representations, 10 and 2.

To add the two numbers represented in this way, simply add them to the digital form without hyphenation. It is clear that we can do this effectively in parallel (with a linear dimension, a constant depth pattern). Well, now we have a problem: the resulting number has the correct base-2 value, but its numbers will not necessarily be 0, 1, or 2, but they can be 4.

So, let's fix this with the following transfer carry: Write each digit of the result as a binary number with two digits, where the second digit is 0 or 1, and the first digit can be 0, 1 or 2. (So 0 → 00, 1 → 01, 2 → 10, 3 → 11, 4 → 20.) Now "transfer" the first digit of each of these two-digit numbers to the left, leaving the second digit, but without performing any other results. For example, if we started with a number

  314102 (perhaps from the original problem of computing 212001 + 102101) 

we carry out the amount

 11 = 3 01 = 1 20 = 4 01 = 1 00 = 0 10 = 2 ------- 1130110 

The new number has the same base-2 value, and its digits are now in the range from 0 to 3, since they are formed from the sum of the digits 0, 1 or 2 and a digit that is 0 or 1. In addition, each digit of the result depends only from the corresponding digit and the digit from its right number from the step, so this can be realized using another linear constant depth circuit.

This is not entirely good, so let the same propagation transfer go through again. Now 4 is no longer a possible input digit, so the digit we carry can never be 2, only 0 or 1. Therefore, this time the procedure will lead to a base 2 representation that uses only the digits 0, 1 and 2, this is what we wanted. In the example above, the result will be 1210110 . (Of course, any other representation with the same base-2 value would also be correct.)

(For other combinations of the base and maximum digits, you may need only one distribution transfer. For example, if you represent numbers in base 3 using the digits 0, 1, 2, 3, and 4, the largest digit appears in the sum is 8, so both digits, participating in the transfer will be in the range 0, 1, 2, and their sum will be no more than 4.)

---

Now, if you want to perform other operations on this representation, for example, comparing two numbers for equality, one option is to convert to binary, either serially in linear time, or in parallel, using a quick adder, as described in Lior Kogan's answer . In fact, converting this representation into a binary file is essentially equivalent to the task of adding numbers in binary form, since we can consider a representation of type 212001 as a “formal complement” of 101000 + 111001 . However, you probably cannot verify equality in this representation at a constant depth, as you can for binary. I believe that "hardness" in this sense of either adding or checking equality is important given your other limitations, although I don’t know for sure.

Answer 3

One simple way to describe the parallel addition of natural numbers is this: if you look at the complete adder circuit, it has 3 input bits and it outputs a 2-bit number indicating how many of the input bits were 1. That is why it is sometimes called a 3: 2 compressor . From these, we can create a circuit that adds 3 binary numbers in parallel to produce 2 binary numbers. This is also called the carry-save adder scheme because instead of distributing the carry bits we save them as a separate separate number. Each number is then (redundantly) represented as a pair of binary numbers. And when adding k natural numbers at each step, we can reduce triplets to tuples, requiring only O (log k) time steps.

But the problem is that if we are limited only to ADT, we have a fixed set of constructors, each of which has a finite number of records. Thus, regardless of the depth of this structure will be equal to O (log n). And we have to follow O (log n) steps to traverse the structure.