Okay so i need really FAST algorithm or code in C if you have any it would be nice. The task is to sum all numbers from 1 to N for a given number N (it can be negative number too), so i did the usual way (you know just summing with loop from 1 to N) but it's not fast enough - i need something faster, i guess that i need the fastest possible way to do this.
If anyone could help me, please do. Thanks.
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);.
Try this...
Where n is the maximum integer you need to sum to.
The sum is (n*(N+1))/2
To deal with integer overflow I'd use the following function:
sum = (N%2) ? ( ((N+1)/2)*N ) : ( (N/2)*(N+1) );
int sum(int n) {
return (n < 0 ? n *(-n + 1) / 2 + 1 : 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)
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.