10

在执行具有小精度浮点数的算术运算时，我检测到异常的计算时间。以下简单代码展示了这种行为：

#include <time.h>
#include <stdlib.h>
#include <stdio.h>

const int MAX_ITER = 100000000;

int main(int argc, char *argv[]){
    double x = 1.0, y;
    int i;
    clock_t t1, t2;
    scanf("%lf", &y);
    t1 = clock();
    for (i = 0; i < MAX_ITER; i++)
        x *= y;
    t2 = clock();
    printf("x = %lf\n", x);
    printf("Time: %.5lfsegs\n", ((double) (t2 - t1)) / CLOCKS_PER_SEC);
    return 0;
}

这是程序的两种不同运行：

  • y = 0.5

    x = 0.000000
    时间：1.32000segs

  • y = 0.9

    x = 0.000000
    时间：19.99000segs

我正在使用具有以下规格的笔记本电脑来测试代码：

  • CPU : Intel® Core™2 Duo CPU T5800 @ 2.00GHz × 2
  • 内存：4 GB
  • 操作系统：Ubuntu 12.04（64 位）
  • 型号：戴尔工作室 1535

有人可以详细解释为什么会发生这种行为吗？我知道 y = 0.9 时 x 值变为 0 的速度比 y = 0.5 时要慢，所以我怀疑问题与此直接相关。

4

2 回答 2

10

非正规（或者更确切地说是次正规）数字通常会影响性能。0根据您的第二个示例，缓慢收敛到将产生更多的次常态。在此处和此处阅读更多信息。如需更认真的阅读，请查看经常被引用（并且非常密集）的What Every Computer Scientist Should Know About Floating-Point Arithmetic。

从第二个来源：

在 IEEE-754 下，浮点数以二进制表示为：

Number = signbit \* mantissa \* 2exponent

可能有多种表示相同数字的方式，以十进制为例，数字 0.1 可以表示为 1*10-1 或 0.1*100 甚至 0.01 * 10。标准规定数字始终与第一位作为一个。对应于 1*10-1 示例的十进制。

现在假设可以表示的最低指数是-100。所以可以用范式表示的最小数是1*10-100。但是，如果我们放宽前导位为 1 的约束，那么我们实际上可以在同一空间中表示较小的数字。以十进制为例，我们可以表示 0.1*10-100。这称为次正规数。具有次正规数的目的是为了平滑最小正规数和零之间的差距。

认识到次正规数的表示精度低于正规数是非常重要的。事实上，他们正在以较小的尺寸换取较低的精度。因此，使用次正规数的计算不会具有与正规数计算相同的精度。因此，对次正规数进行大量计算的应用程序可能值得研究，以查看重新缩放（即将数字乘以某个缩放因子）是否会产生更少的次正规数和更准确的结果。

我正在考虑自己解释它，但上面的解释写得非常好和简洁。

于 2012-09-12T17:44:57.543 回答
3

您得到可测量的差异不是因为0.9^n收敛到 0 的速度比0.5^n数学上慢，而是因为在 IEEE-754 浮点实现中，它根本不会收敛到 0。

doubleIEEE-754 表示中最小的正数是 2 -1074 ，最小的正数是 2 -1021，所以对于y = 0.5，循环遇到 53 个次正规数。一旦达到最小的正次正规，下一个乘积将是 2 -1075，但由于舍入到最后一位零的默认舍入模式，舍入为 0。（浮点数的IEEE-754表示并且默认的 round-ties-to-last-bit-zero 舍入模式在标准消费类硬件上几乎无处不在，即使标准没有完全实现。）从那时起，你就有了一个乘法0*y，它是一个普通的浮点乘法（即使y是次等数也很快）。

使用0.5 < y < 1，一旦您达到（正）次正常范围的下限，结果将再次舍入x*y到 的值x（对于y = 0.9，迭代的固定点是 5*2 -1074）。由于这是在几千次迭代 ( 0.9^7 < 0.5) 之后达到的，因此对于整个循环，您基本上是在将一个次正规数与一个非零数相乘。在许多处理器上，这样的乘法不能直接处理，必须在微码中处理，这要慢得多。

如果速度比 IEEE-754 语义更重要（或者如果出于其他原因不希望这样做），许多编译器会提供选项来禁用该行为并将次正规数刷新为 0（如果硬件支持）。我在我的 gcc 的手册页中找不到明确的选项，但-ffast-math在这里做了诀窍。

于 2012-09-12T19:31:35.830 回答