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

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

这将 return 您的计算机使用的基础（很可能是 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 个零。这受到 machines/language/type 精度的限制。当 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)，但当然，那会是作弊（因为我们不知道先验的基础）。

How and why does this algorithm find the floating point base value of your computer?