sum.js

/**
 * 我们的默认求和算法是 [Kahan-Babuska算法](https://pdfs.semanticscholar.org/1760/7d467cda1d0277ad272deb2113533131dc09.pdf)。
 * 该算法是对经典的 [Kahan求和算法](https://en.wikipedia.org/wiki/Kahan_summation_algorithm) 的改进。
 * 它旨在计算一组数字的总和，同时纠正浮点误差。传统上，求和是通过多次连续的加法运算来完成的，每次加法都会产生自己的浮点舍入误差。
 * 随着数字数量的增加，这些精度损失会累积。该替代算法比简单的加法求和更精确。
 *
 * 该算法的时间复杂度为 `O(n)`，即线性时间，与数组的长度成正比。
 *
 * @param {Array<number>} x 输入数组
 * @return {number} 所有输入数字的总和
 * @example
 * sum([1, 2, 3]); // => 6
 */
function sum(x) {
    // 如果数组为空，我们无需计算其总和
    if (x.length === 0) {
        return 0;
    }

    // 将数组中的第一个数字初始化为总和
    let sum = x[0];

    // 跟踪浮点误差校正
    let correction = 0;

    let transition;

    if (typeof sum !== "number") {
        return Number.NaN;
    }

    for (let i = 1; i < x.length; i++) {
        if (typeof x[i] !== "number") {
            return Number.NaN;
        }
        transition = sum + x[i];

        // 如果新的绝对值大于当前总和的绝对值，我们需要以不同的方式更新校正值
        if (Math.abs(sum) >= Math.abs(x[i])) {
            correction += sum - transition + x[i];
        } else {
            correction += x[i] - transition + sum;
        }

        sum = transition;
    }

    // 返回校正后的总和
    return sum + correction;
}

export default sum;