We must show how N binary numbers, each consisting of N bits each, can be added in a linear grid of N+logN processors. Suppose that the binary digits can be inserted directly in each processor of the grid.

Give the upper limit for the steps that are necessary and state your answer in short.

Can you check my answer? This is what I've done so far:

  • We have the grid of N+logN processors.

N processors correspond to N bits and the rest logN processors are used for saving the extra bits that occur from the add function (each addition produces a carry bit - {0,1} ).

While adding 2 numbers and because of the delay of the ripple-carry we have that:

  • for adding bits a(i)+b(i) we have to wait i steps until the carry bit is passed through the last significant bit (i-th position to be exact).

BUT, during these i steps we can execute additions to the former levels/tiers. So the carry of adding a(i)+b(i) will be produced in i steps and we can see it in this sketch: enter image description here

We can see that the carry from adding A= a(0)a(1)a(2)...a(N-1) and B=b(0)b(1)...b(N-1) travels through the main (or major as some call it) diagonal. After N+logN steps the carry will have reached to the cell that has the sum of the A and B MSB(most significant bit), so the addition will be over.

Right after that, in the next time slot the last carry will reach last row we are using of the addition of S+C where S=A+B and C=c(0)c(1)...c(N-1) and we will have the result of A+B+C.

So we have N-1 steps for the carries to reach the last slots so the required time is:

  • N+logN+N-1 steps

Do I state it right or is something missing?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.