发布于 由admin

JavaScript 的数值计算精度：Kahan 求和算法在处理大量浮点数累加时的应用

各位同学，各位同仁，大家好！

今天，我们将深入探讨一个在日常编程中常常被忽视，但在处理大量数值数据时又至关重要的话题：JavaScript 中的浮点数计算精度。特别是，我们将聚焦于一个巧妙的算法——Kahan 求和算法，来解决在累加大量浮点数时可能出现的精度损失问题。

浮点数：数字世界的“近似”与挑战

在JavaScript（以及大多数现代编程语言）中，数字的表示遵循 IEEE 754 双精度浮点数标准。这意味着每个数字都由64位二进制数来存储，其中包括一个符号位、一个指数位和一个尾数（或称有效数字）位。这种表示方法在很大程度上能够高效地表示非常大或非常小的数字，但它并非没有代价。

问题根源：二进制无法精确表示所有十进制小数

浮点数的本质是使用二进制分数来近似表示实数。就像十进制分数 1/3 无法在有限位数的十进制中精确表示为 0.333... 一样，许多简单的十进制小数，如 0.1，也无法在二进制中被精确表示。

例如，十进制的 0.1 在二进制中是一个无限循环小数：
0.00011001100110011...

由于计算机的存储空间有限，它必须在某个点截断这个无限序列，这就引入了微小的舍入误差。单个的舍入误差通常非常小，对大多数计算来说可以忽略不计。但当这些微小的误差在一系列计算中累积起来时，就可能导致最终结果与预期值产生显著偏差。

让我们看一个经典的JavaScript浮点数问题：

console.log(0.1 + 0.2);
// 预期结果：0.3
// 实际输出：0.30000000000000004

这个结果令人惊讶，但它直接揭示了浮点数计算的内在特性。0.1 和 0.2 都不能被精确表示，它们各自都有一个微小的舍入误差。当它们相加时，这些误差被合并，并且在结果中以一个微小的偏差显现出来。

IEEE 754 双精度浮点数概述

为了更好地理解精度问题，我们有必要简要回顾一下 IEEE 754 双精度浮点数的结构。一个64位的双精度浮点数被分解为三个部分：

  1. 符号位 (Sign Bit): 1位，表示数字的正负（0为正，1为负）。
  2. 指数位 (Exponent): 11位，用于表示小数点的位置，决定了数字的量级。通过一个偏移量（bias）来处理正负指数。
  3. 尾数/有效数字位 (Mantissa/Significand): 52位，用于表示数字的精确值。由于浮点数通常以规范化形式存储（即假定小数点前有一位非零数字，通常是1），所以这52位实际上提供了53位的精度（隐含的最高位1）。

这种结构允许表示的数字范围非常广，从大约 5e-324 到 1.8e+308。然而，它也意味着在任意两个可表示的浮点数之间存在着“间隙”。这些间隙的大小随着数字的绝对值增大而增大。

关键概念：机器精度 (Machine Epsilon)

Number.EPSILON 是 JavaScript 提供的一个常量，它代表了1与大于1的最小浮点数之间的差值。在双精度浮点数中，它大约是 2.220446049250313e-16。它衡量了浮点数计算的相对精度。当两个数字的差值小于或等于 EPSILON 乘以其中较大数字的绝对值时，它们可能被认为是相等的，或者说，它们的差异已经超出了浮点数可以区分的最小单位。

部分 位数 描述
符号位 1 0表示正数，1表示负数
指数位 11 决定数字的量级，范围约从 -1022 到 1023
尾数位 52 决定数字的精确值，提供约15-17位十进制精度

正是由于这种有限的精度和间隙的存在，当我们在进行大量浮点数累加时，问题就会变得尤为突出。

朴素求和的陷阱：误差的累积与吞噬

最直观的求和方法就是简单地将所有数字逐个相加：

function naiveSum(numbers) {
    let sum = 0;
    for (let i = 0; i < numbers.length; i++) {
        sum += numbers[i];
    }
    return sum;
}

这种方法在大多数情况下都表现良好，但当满足以下两个条件时，它会暴露出严重的精度问题：

  1. 累加的数字数量非常大。
  2. 要累加的数字大小差异悬殊。 例如，将大量非常小的数字累加到一个非常大的数字上。

误差吞噬 (Loss of Significance)

当一个非常小的浮点数被添加到一个非常大的浮点数时，小数字的有效位可能会完全丢失。这是因为在执行加法操作之前，计算机需要调整这两个数字的指数，使它们的有效数字对齐。如果两个数字的量级相差太大，小数字的有效位可能会被“右移”到超出尾数所能表示的范围，从而被舍弃。

举一个例子：
假设我们有一个非常大的数 A = 1.0000000000000000e+15 和一个非常小的数 B = 1.0e-1。
当我们计算 A + B 时：
1.0000000000000000e+15
+ 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
The difference between A and A + B is so small that it falls within the rounding precision of A. The effectively A + B = A.

实际案例：
假设你正在模拟一个粒子系统，需要对数百万个粒子在每个时间步长的能量进行累加。如果每个粒子的能量都是一个微小数，而总能量可能非常大，那么朴素求和将迅速积累误差。

// 模拟一个场景：将大量小值加到一个大值上
const NUM_ITERATIONS = 1000000;
const largeValue = 1000000000000000; // 一个非常大的数
const smallValue = 0.0000000000000001; // 一个非常小的数

let numbersToSum = [largeValue];
for (let i = 0; i < NUM_ITERATIONS; i++) {
    numbersToSum.push(smallValue);
}

const naiveResult = naiveSum(numbersToSum);
const expectedApproximateResult = largeValue + NUM_ITERATIONS * smallValue; // 理论上的精确和

console.log("--- 朴素求和示例 ---");
console.log("大值:", largeValue);
console.log("小值:", smallValue);
console.log("累加次数:", NUM_ITERATIONS);
console.log("理论近似和:", expectedApproximateResult);
console.log("朴素求和结果:", naiveResult);
console.log("朴素求和误差:", Math.abs(naiveResult - expectedApproximateResult));
// 实际运行，你会发现 naiveResult 会比 expectedApproximateResult 小很多，
// 甚至可能就是 largeValue 本身，因为所有 smallValue 都被“吞噬”了。

当 smallValue 足够小，而 largeValue 足够大时，naiveResult 的输出可能就是 largeValue，这意味着所有 NUM_ITERATIONS 次 smallValue 的贡献都被完全抹杀了，这是一个灾难性的精度损失。

Kahan 求和算法：补偿式求和

为了应对这种累积的舍入误差，W. Kahan 在1960年代提出了一种精巧的解决方案，被称为 Kahan 求和算法（Kahan summation algorithm），也称作补偿式求和（compensated summation）。

Kahan 算法的核心思想是：在每一次加法操作中，不仅仅是更新总和，还要记录因为舍入而“丢失”的那一部分值，并在下一次迭代中将其补偿回来。通过这种方式，即使每次丢失的量很小，它们也会被追踪并最终被加回到总和中，从而显著提高累加的精度。

算法变量：

  • sum: 当前的累加总和。
  • input: 当前要加入总和的数字。
  • y: 经过补偿后的 input。
  • t: 临时总和，用于计算新的 sum。
  • c: 补偿值（compensation），记录了上次加法中丢失的低位信息。

Kahan 算法的步骤：

  1. 初始化 sum = 0.0 和 c = 0.0。
  2. 对于序列中的每个数字 input：
    a. 计算 y = input - c。y 是当前数字减去上一次加法中丢失的补偿值。这样

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注