Fastest possible algorithm to sum numbers up to N

问题:

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.

回答1:

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);.

回答2:

sum = N * (N + 1) / 2

回答3:

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.

回答4:

Just to complete the above answers, this is how you prove the formula (sample for positive integer but principle is the same for negatives or any arithmetic suite as Void pointed out).

Just write the suite two times as below and add 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)

回答5:

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

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

回答6:

Try this...

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

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

回答7:

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

回答8:

have you heard about sequence & series ? The 'fast' code that you want is that of sum of arithmetic series from 1 to N .. google it .. infact open your mathematics book..

回答9:

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.