卡汉求和算法

在数值分析中，卡汉求和算法也被称为补偿求和，与明显的方法相比，卡汉求和算法xxx减少了通过添加一串有限精度浮点数得到的总数的数值误差。这是通过保留一个单独的运行补偿来实现的，实际上是通过补偿变量的精度来扩展和的精度。特别是，简单地将的最坏情况下的误差。其均方根误差增长为n对于随机输入。通过补偿求和，使用具有足够高的精度的补偿变量，最坏情况下的误差界限实际上是独立于n，所以大量的值可以被用来计算。因此，大量的数值可以被求和，其误差只取决于结果的浮点精度。

这个算法也可以改写为使用Fast2Sum算法。varc=0.0//对丢失的低阶比特进行运行补偿。丢失的低阶部分将被重新加入y中。

这个例子将用十进制给出。计算机通常使用二进制算术，但所说明的原理是一样的。假设我们使用的是六位数的十进制浮点运算，sum已经达到了10000.0的值，输入[i]的下两个值是3.14159和2.71828。准确的结果是10005.85987，四舍五入为10005.9。如果是普通的求和，每个传入的值都会与sum对齐，许多低阶数字会丢失（通过截断或舍入）。xxx个结果，四舍五入后，将是10003.1。第二个结果在舍入前是10005.81828，舍入后是10005.8。这是不正确的。然而，通过补偿求和，我们得到正确的四舍五入结果10005.9。假设c的初值为零。和是如此之大，以至于只有输入数字的高阶数字被累积。

求和是用两个累加器进行的：sum保持总和，c累加没有被同化到sum中的部分，以便在下次求和的时候推算出低阶部分。因此，求和过程中，c中含有保护位，这比没有保护位要好，但还不如以输入的两倍精度进行计算好。