驯服浮点数求和 | orlp.net

主要观点:介绍了多种对浮点数数组求和的方法,包括朴素求和(naive sum)、成对求和(pairwise summation)、卡汉求和(Kahan summation)、精确求和(exact summation)等,还提到了 Rust 编译器相关的问题及解决方法,比较了不同求和方法在速度和精度上的差异。

关键信息:

  • 朴素求和易产生累积误差,如对大量 1.0 求和结果出现异常。
  • 成对求和更准确但速度较慢,可通过分块处理提高速度。
  • 卡汉求和能进一步降低误差,结合分块处理可提高效率。
  • 精确求和有基于 2Sum 或整数缓冲的方法,可精确求和但需额外内存。
  • Rust 编译器不允许重排浮点数加法,导致无法自动向量化求和,新的fadd_algebraic运算符可解决此问题,能实现自动向量化求和且速度快。
  • 比较不同求和方法的性能和精度,block_kahan_autovec在速度和精度间取得较好平衡,通过分块处理可进一步提高性能。

重要细节:

  • 机器epsilon 对不同求和方法误差的影响,如朴素求和误差为$O(n \\epsilon)$等。
  • 各种求和方法的代码实现细节,如成对求和的递归方式、卡汉求和的双寄存器维护等。
  • 不同求和方法在不同数据规模下的性能表现,如对 100,000 随机浮点数求和的结果。
  • Rust 中相关编译器 intrinsics 的使用及注意事项,如std::intrinsics::fadd_fast的危险性等。
阅读 29
0 条评论