此算法如何以及为什么找到您计算机的浮点基值？

Question

伪代码中的算法：

float a = 1
while (a + 1) - a == 1
    a = 2 * a

int i = 1
while (a + i) == a
    i = i + 1

return (a + i) - a

这将返回您的计算机使用的基准（很可能是2）。变量a必须为浮点型或双精度型才能起作用。

我不知道为什么以及它如何工作。

Answer 1

这是一种搜索算法，搜索（几乎）第一个浮点数不能再连续代表所有整数。为了使阅读更容易，我们假设基数为10。(a+1) - a != 1是什么意思？标记

a=s*10^e

其中s是有效数字，e是指数。然后：

a+1=s*10^e + 1*10^0 = s*10^e + (1/10^e)*10^e=(s+1/10^e)*10^e

现在1/10^e = 1 * 10^-e是0.0000...1，其中有e个零。这受机器/语言/类型精度的限制。当e足够大时，它将仅为0。因此，第一个循环找到了发生的第一个（ish）数字之一。

现在，第二个循环找到第一个整数，它将其添加到a中，这是机器会注意到的东西，a的下一个可表示值。首先让我们猜测这个整数是10的基数。然后有：

a + i = s*10^e + 10 = 10*(s*10^(e-1) + 1)

[我们知道可以表示RHS，因为e是加1不可表示的第一个指数（因此e-1是），乘以基数（10）只是将指数加1。让我们尝试一个较小的整数：

a+9=s*10^e + (9/10^e)*10^e = (s + 9/10^e)*10^e

0.000....9需要与1/10^e = 0.000...1相同的精度以不同于0，因此不会更改a的值。这也清楚地表明了另一种方式来显示i=10是足够的第一个整数-我们将拥有10/10^e=1/10^(e-1)，由于第一个循环，它再次可以表示。

最后，仅打印i就足够了。

注意，此方法适用于任何基础，以10为基础（以熟悉的方式表示1/10^e=0.000...1）更容易编写。还要注意，我们不必依赖a = 2*a，也就是说，就像您遇到的那样，a是基数的幂。它将简化上面的部分（s=1），但是，那当然是作弊的（因为我们不知道先验的基础）。