The fastest algorithm for summing numbers to N

Question

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

Answer 1

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

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

Answer 2

 sum = N * (N + 1) / 2 

Answer 3

The formula you are looking for is a more general form, published in several answers to your question, which is an Arithmetic Series / Progression with a difference factor of 1 . From Wikipedia , this is the following:

The above formula will handle negative numbers if m is always less than n. For example, to get the sum from 1 to -2, set m to -2 and n to 1, that is, the sum from -2 to 1. This results in:

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

which is the expected result.

Answer 4

To complete the above answers, you prove the formula (the sample is for a positive integer, but the principle is the same for negatives or any arithmetic set, as Void pointed out).

Just write the package two times below and add the numbers:

  1+ 2+ 3+ ... n-2+ n-1+ n = sum(1..n) : n terms from 1 to n + n+ n-1+ n-2+ ... 3+ 2+ 1 = sum(n..1) : the same n terms in reverse order -------------------------------- n+1+ n+1+ n+1+ ... n+1+ n+1+ n+1 = 2 * sum(1..n) : n times n+1 n * (n+1) / 2 = sum(1..n) 

Answer 5

To handle integer overflow, I would use the following function:

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

Answer 6

Try it...

Where n is the maximum integer to be added.

Sum (n * (N + 1)) / 2

Answer 7

int sum(int n) { return (n < 0 ? n *(-n + 1) / 2 + 1 : n * ( n + 1) / 2); }

Answer 8

Have you heard about sequence and series? The “quick” code you want is the sum of arithmetic series from 1 to N .. google it .. infact open your math book.

Answer 9

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

or using the cache, first search the cache if you cannot find the record, and then recoup the amount using n * (n + 1) / 2 (if n is positive) and write the result in the cache.