将 N 以内的数字相加的最快算法

Question

我想要一个真正快速的 C 算法或代码来完成以下任务：对于任何给定的整数 N，对从 1 到 N 的所有数字求和，而不假设 N 为正数。我做了一个从 1 到 N 求和的循环，但是太慢了。

Answer 1

如果N为正数：int sum = N*(N+1)/2;

如果N为负数：int tempN = -N; int sum = 1 + tempN*(tempN+1)/2 * (-1);。

Answer 2

sum = N * (N + 1) / 2

Answer 3

您正在寻找的公式是在您的问题的多个答案中发布的公式的更通用形式，这是一个 算术级数/级数，差异因子为1。来自维基百科，如下：

只要 m 始终小于 n，上述公式就会处理负数。例如，要获得从 1 到 -2 的总和，请将 m 设置为 -2，将 n 设置为 1，即从 -2 到 1 的总和。这样做会导致：

(1 - -2 + 1) * (1 + -2) / 2 = 4 * -1 / 2 = -4 / 2 = -2.

这是预期的结果。

Answer 4

为了完成上述答案，这就是证明公式的方法（正整数的示例，但原理与负数或 Void 指出的任何算术套件相同）。

只需将套件写两次，如下所示并添加数字：

  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 5

为了处理整数溢出，我将使用以下函数：

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

Answer 6

试试这个...

其中 n 是您需要求和的最大整数。

总和为 (n*(N+1))/2

Answer 7

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

Answer 8

你听说过顺序和顺序吗？系列 ？你想要的“快速”代码是从 1 到 N 的算术级数之和..谷歌它..事实上打开你的数学书..

Answer 9

如果|n|足够小，查找表将是最快的。

或者使用缓存，首先查找缓存，如果找不到记录则使用n * (n + 1) / 2（如果n为正数）计算总和，并将结果记录到缓存中。