Sum (i ... j) - is there a more efficient / elegant solution for this?

Question

We were given a simple task - to find the most efficient way to sum all numbers between the start and end points (from "and" to ")" using recursion and iteration, respectively, without using an obvious formula that would be O (1).

There is no application for this, I'm just curious and hard to understand if my solution can be improved / polished more than it is:

/* recursion */ unsigned int sum1(unsigned int from, unsigned int to) { if (to - from < 2) return from + (from == to ? 0 : to); else return from + to + sum1(from + 1, to - 1); } /* iteration */ unsigned int sum2(unsigned int from, unsigned int to) { int p = to - from; if (p == 0) return from; int i, s, n = p / 2; if (p % 2 == 0) s = n + from; else { s = 0; n++; } for (i = 0; i < n; i++) { s += from++ + to--; } return s; } 

Answer 1

I tried to improve the iterative version:

 unsigned int sum2_improved(unsigned int from, unsigned int to) { int p = to - from; if (p == 0) return from; int x = to + from; int s = 0; int i; for (i = p >> 1; i > 0; i--) { s += x; } s += (p % 2 == 0) ? x >> 1 : x; return s; } 

I tested your version with:

 for (i = 0; i < 9999999; i++) sum2(1,999); 

Here is what I see:

 $ time ./addm real 0m18.315s user 0m18.220s sys 0m0.015s 

I tried my implementation with the same number of loops. Here, how the improved function is implemented:

 $ time ./addm real 0m14.196s user 0m14.070s sys 0m0.015s 

---

UPDATE

In my implementation, x = to + from is the sum of the first and last number in the sequence. If you consider any consecutive sequence of integers and sum the first and last, second and second to last, etc ... all these sums coincide with the same value. For example, in (1 ... 6), 1 + 6 = 2 + 5 = 3 + 4 = 7 . However, with a sequence containing an odd number of elements, you are left with the average number that you will need to add to the total (which is what was done after the for loop.

Also note that this is still O(n) . I realized that after I stated my answer, my approach can indeed be carried out in a constant time. Here's the updated code:

 unsigned int sum0(unsigned int from, unsigned int to) { int p = to - from; if (p == 0) return from; int x = to + from; int s = 0; s += (x * (p >> 1)); s += (p % 2 == 0) ? x >> 1 : x; return s; } 

I ran this with the same number of loops as the previous tests. Here is what I saw:

 $ time ./addm real 0m0.158s user 0m0.093s sys 0m0.047s 

I am not sure if this can be considered as a variant of the formula for your purposes. In any case, it was an interesting exercise for me.

Answer 2

Divide the range (from zero to the upper limit n) in the lower and upper half. For each value in the lower half, there is a value in the upper half that is greater than n / 2; there are n / 2 of them, so the sum of the upper half is equal to the sum of the lower half + (n / 2) ^ 2.

In Python, this will be:

 def sum1(lower, upper): if upper <= 0: return 0 m, r = divmod(upper, 2) return sum1(0, m) * 2 + m * m + r * upper - sum1(0, lower - 1) 

Answer 3

I am not going to write code for it, but this is the type that will directly scale with the number of cores that you are working on.

Dividing the range into tasks and starting the stream to summarize each subsection of the range will divide the time required for any implementation that you choose according to the number of cores (give or take).

You can also use SIMD extensions to facilitate adding (adding vectors) by writing data to memory before starting work. Taking this to the other extreme, you could actually use the GPU to compute the addition of sub-bands (but you would need to have a large enough range to make it useful overhead), which makes it stupidly fast; as this question is as simple as you can get without any dependencies between instructions.

Answer 4

You can use the segment tree to get the sum on the segment from i to j. This structure has an O (log n) lookup time.

Answer 5

Function:

 long sum(long lower, long upper) { long s = 0; s = ((upper * (upper + 1)) - (lower - 1) * (lower))/2; return s; } 

with parameters: (1,9999999) returns 49999995000000, which is consistent with the summation formula n (n + 1) / 2 and works with the following profile on the kernel core:

 real 0m0.005s user 0m0.002s sys 0m0.003s 

It might be worth checking your functions, I don’t see them returning this result - a mathematical option is a much better solution;)