Fastest possible algorithm to sum numbers up to N [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad,开发者_运维知识库 or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 10 years ago.

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.