The 2-3 trick for summing n numbers of d-bits each in log 2/3 n steps

1- Patition the remainining n numbers to n/3 groups of three numbers each.

2- Temporary devide each number x_i to two numbers of d-bits each:

xa_i containg the odd bits of x_i and xb_i containg the even bits

of x_i. Thus each group contains six numbers accordingly.

3- In parallel for each group sum the three odd numbers and the three

even numbers seperatly.

This is done by summing in parallel each bit. For example,

assume that we are to sum the j'th bit of xa_i,xa_i+1,xa_i+2

where j=0,2,4,8,.... .

Since the even place j+1 is empty then the tree bits can be easily summed

(yieliging either 00,01,10 or 11) and their carry can be safely stored

in the j+1 bit.

4- At this stage each group is reduced to two numbers

ya_i,yb_i containg the odd/even sums of the original three numbers

xa_i,xa_i+1,xa_i+2.

5- We can reat thise steps with the remaining numbers setting

x_1,...,x_2n/3 to ya_1,yb_1,ya_3,yb_3,....

Each application of these steps reduces the remaining numbers by 2/3

hence after log 2/3 n we can compute the total sum.