Fastest possible algorithm to sum numbers up to N

Question

I want a really fast algorithm or code in C to do the following task: sum all numbers from 1 to N for any given integer N, without assuming N is positive. I made a loop summing from 1 to N, but it is too slow.

Answer 1

sum = N * (N + 1) / 2

Answer 2

Try this...

Where n is the maximum integer you need to sum to.

The sum is (n*(N+1))/2

Answer 3

If N is positive: int sum = N*(N+1)/2;

If N is negative: int tempN = -N; int sum = 1 + tempN*(tempN+1)/2 * (-1);.

Answer 4

The formula you're looking for is a more general form of the one posted in multiple answers to your question, which is an Arithmetic Series/Progression with a difference factor of 1. From Wikipedia, it is the following:

The above formula will handle negative numbers as long as m is always less than n. For example to get the sum from 1 to -2, set m to -2 and n to 1, i.e. the sum from -2 to 1. Doing so results in:

(1 - -2 + 1) * (1 + -2) / 2 = 4 * -1 / 2 = -4 / 2 = -2.

which is the expected result.

Answer 5

To deal with integer overflow I'd use the following function:

sum = (N%2) ? ( ((N+1)/2)*N ) : ( (N/2)*(N+1) );

Answer 6

if |n| is small enough, a lookup table will be the fastest one.

or using a cache, first search the cache, if can't find the record then caculate the sum by using n * (n + 1) / 2(if n is positive), and record the result into the cache.