Fastest possible algorithm to sum numbers up to N [closed]
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.
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);
.
sum = N * (N + 1) / 2
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.
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)
To deal with integer overflow I'd use the following function:
sum = (N%2) ? ( ((N+1)/2)*N ) : ( (N/2)*(N+1) );
Try this...
Where n is the maximum integer you need to sum to.
The sum is (n*(N+1))/2
int sum(int n) {
return (n < 0 ? n *(-n + 1) / 2 + 1 : n * ( n + 1) / 2);
}
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..
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.
精彩评论