Fastest possible algorithm to sum numbers up to N

Question

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.

Answer 1

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)

Answer 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..

Answer 3

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