Big number addition problem

Accelerated Computing CUDA CUDA Programming and Performance
1

I have lots of big numbers represented by two parts: one is 4 bytes integer/float, the other is left shift offset. Left shift number is like 0, 1, 1, 2, 2, 3, 4, 5, 5, … , each number at least shows once, all big numbers can have same left shift offset. Let F denote the frequency of each offset, 1 <= F <= N, N is number of all big numbers.

For example: I have 4 big number, N = 4, 1 <= F <=4.
left shift number : 0 , 1, 1, 2,
4 byte Integer : 0x01FFFFeFF, 0x01FFFFeFF , 0x01FFFFeFF, 0x01FFFFeFF

Or we can represent as below, the first number left shift 2 bytes compared with the last one, looks 4 offset since FF represents one byte, hope it is clear.

1FFFFeFF
1FFFFeFF
1FFFFeFF
1FFFFeFF

Any body have any efficient way to resolve the problem? Thanks a lot.

2 
For example: I have 4 big number, N = 4, 1 <= F <=4.

left shift number :        0 ,            1,        1,           2,         

4 byte Integer    : 0x01FFFFeFF, 0x01FFFFeFF , 0x01FFFFeFF, 0x01FFFFeFF

Or we can represent as below, the first number left shift 2 bytes compared with the last one, looks 4 offset since FF represents one byte, hope it is clear.

1FFFFeFF

  1FFFFeFF

  1FFFFeFF

    1FFFFeFF
3

You could use 64-bit accumulators, one for each possible shift count (you did not indicate the range of possible shift counts, I assume it is fairly small). At the end of the process, you would then add the appropriately shifted accumulators to each other. 64-bit adds are quite efficient requiring only two 32-bit adds. 64-bit shifts with variable shift count on the other hand require about eight instructions. So you would want to avoid shifting the data prematurely (I assume that the left-shifted result of the 32-bit data can overflow the 32-bit range, requiring a 64-bit shift). Conceptually:

struct {

   unsigned int val;

   int shift;

} data[N];

unsigned long long acc[MAX_SHIFT+1];

unsigned long long res = 0;

for (int i = 0; i < N; i++) {

    acc[data[i].shift] += data[i].val;

}

for (int i = 0; i <= MAX_SHIFT; i++) {

    res += acc[i] << i;

}
4

HI njuffa, shift could be X milions, any better idea?

5

Not off the top of my head. It might help to give a bit more context as to the task at hand, or at least provide as precise a specification as possible. For example, is the sequence of shift counts give by data[i].shift monotonically increasing as ‘i’ increases? If so, what is the biggest gap between consecutive shift counts that can occur?