sum up an array in the special style of reduction | (i * 2)

Question

I am currently sitting on a java problem I've found online.

---

We have an array which has several thousand, if not millions, of entries. the goal is to efficiently get the full sum of the array.

The first way is to simply sum the values up. This is how I've solved it:

for (int i = 0; i < array_size; i++) sum += array[i];

The other way is the hard way. In the online task, it is described to use some kind of reduction. you should add up all the neighboring elements, then add up every second, then every fourth and so on. Until you arrive at [0] + [max] at the end, [0] has the total sum of the array.

If someone could help me or steer me in the right direction, I would be very grateful.

---

EDIT:

I solved it.

int i = 1;
while (i <= array_size) {

    for (int j = 0; j < array_size - i; j += i) {

        x[j] += x[j + i];

    }

    i *= 2;
}

With this code it would then be possible to parallelize the process. thanks @mtj!

Hope it helps sometime someone else...

Answer 1

Your implementation is already O(n)-time you cannot get better. You need O(1)-space, so this will also not be able to be reduced.

You only could try to improve runtime (not complexity) e.g. by make it more cache friendly or paralize it in hope that this may improve the speed (but for such a simple tasks as adding, I assume that memory-access is a bottle neck).