该算法如何以及为什么找到您计算机的浮点基值?
How and why does this algorithm find the floating point base value of your computer?
伪代码中的算法:
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
必须是浮点数或双精度数才能工作。
我不明白为什么以及它是如何工作的。
这是一种搜索算法,搜索(几乎)第一位的浮点数已经不能连续表示所有整数了。为了便于阅读,我们假设基数是 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
),但当然,那会是作弊(因为我们不知道先验的基础)。
伪代码中的算法:
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
必须是浮点数或双精度数才能工作。
我不明白为什么以及它是如何工作的。
这是一种搜索算法,搜索(几乎)第一位的浮点数已经不能连续表示所有整数了。为了便于阅读,我们假设基数是 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
),但当然,那会是作弊(因为我们不知道先验的基础)。