问题 为什么10 ^ 9942066是我能计算出的最大功率而没有溢出?


在红宝石中,一些大数字大于无穷大。通过二进制搜索,我发现:

(1.0/0) > 10**9942066.000000001 # => false
(1.0/0) > 10**9942066 # => true
RUBY_VERSION # => "2.3.0"

为什么是这样? 10有什么特别之处9942066?它似乎不是像9999999那样的任意数字,它不接近任何两个的幂(它与2大致相等)33026828.36662442)。

为什么红宝石的无限无限?怎么样109942066 参与?


我现在意识到,任何大于10的数字9942066 将溢出到无穷大:

10**9942066.000000001 #=> Infinity
10**9942067 #=> Infinity

但这仍然留下了一个问题: 为什么109942066


4370
now


起源

Ruby的无穷大在数学意义上显然不是无限的。根据定义,它可以处理的最大数量。 - sawa
在数字意义上无法表示真正的无穷大。比较事物与“无限”实际上并不是真正有用的 1/0 是未定义的,而不是“无限”,因为Ruby会让你相信。如果Ruby在数学上是正确的,那么我们最终可以回答“什么是无限加一?”的问题。 - tadman
@sawa显然。但是,它仍然存在9942066来自何处的问题。 - Shelvacu
评估它需要多长时间?我的电脑正在挂,计算 10**9942066。 - sawa
@sawa嗯,确实很熟悉。 - steenslag


答案:


TL; DR

我在里面完成了计算 numeric.cint_pow 手动,检查整数溢出的位置(和Bignum的传播,包括调用 rb_big_pow)发生。一旦打电话给 rb_big_pow 发生在那里检查你是否有两个中间值 int_pow 太大或不太大,截止值似乎只有9942066左右(如果你使用10的基数作为功率)。大约这个值接近

BIGLEN_LIMIT / ceil(log2(base^n)) * n ==
32*1024*1024 / ceil(log2(10^16)) * 16 ==
32*1024*1024 / 54 * 16 ~=
9942054

哪里 BIGLEN_LIMIT 是ruby中的内部限制,用作常量来检查功率计算是否太大,并定义为 32*1024*1024base 是10,和 n 是仍然适合Fixnum的基数的最大2次幂指数。

不幸的是,由于用于计算大数字幂的算法,我找不到比这种近似更好的方法,但是如果你的代码需要在对大数字进行取幂之前检查有效性,那么它可能足够好用作上限。 。


原始问题:

问题不在于9942066,而是您的一个数字是整数,另一个是浮点数。所以

(10**9942066).class # => Bignum
(10**9942066.00000001).class # => Float

第一个可由内部特定数字表示,小于 Infinity。第二个,因为它仍然是一个浮点数不能用实际数字表示,而只是被替换为 Infinity,当然不大于 Infinity

更新的问题:

你是正确的,在9942066周围似乎有一些差异(如果你在Linux下使用64位ruby,因为在其他系统下限制可能会有所不同)。虽然ruby确实使用GMP库来处理大数字,但是在进入GMP之前它会进行一些预检,正如您可以收到的警告所示。它还将使用GMP的mul命令手动执行取幂,而无需调用GMP的pow函数。

幸运的是,这些警告很容易被发现:

irb(main):010:0> (10**9942066).class
=> Bignum

irb(main):005:0> (10**9942067).class
(irb):5: warning: in a**b, b may be too big
=> Float

然后你可以实际检查这些警告在ruby中发出的位置 bignum.c 图书馆。

但首先我们需要进入Bignum领域,因为我们的两个数字都是简单的Fixnums。计算的初始部分和从fixnum到bignum的“升级”在内部完成 numeric.c。 Ruby执行快速取幂,并在每一步检查结果是否仍然适合Fixnum(比系统bitsize小2位:64位机器上的62位)。如果没有,它会将值转换为Bignum领域,并在那里继续计算。我们感兴趣的是这种转换发生的地方,所以让我们试着弄清楚它在我们的时间 10^9942066示例(我在ruby的numeric.c代码中使用x,y,z变量):

x = 10^1  z = 10^0   y = 9942066
x = 10^2  z = 10^0   y = 4971033
x = 10^2  z = 10^2   y = 4971032
x = 10^4  z = 10^2   y = 2485516
x = 10^8  z = 10^2   y = 1242758
x = 10^16 z = 10^2   y = 621379
x = 10^16 z = 10^18  y = 621378
x = OWFL

此时x将溢出(10^32 > 2^62-1),所以这个过程将通过计算继续在Bignum领域 x**y,是的 (10^16)^621378 (在这个阶段实际上它们仍然都是Fixnums)

如果你现在回去 bignum.c 并检查它是如何确定数字是否太大,您可以看到它将检查保持所需的位数 x,并将此数字乘以 y。如果结果大于 32*1024*1024,它将失败(发出警告并使用基本浮点数进行计算)。

(10^16) 是54位(ceil(log_2(10^16)) == 5454*621378 是33554412.这只是略小于33554432(按20),之后红宝石不会做Bignum取幂的极限,而只是转换 y 加倍,希望最好(显然会失败,然后回归 Infinity

现在让我们尝试使用9942067进行检查:

x = 10^1   z = 10^0    y = 9942067
x = 10^1   z = 10^1    y = 9942066
x = 10^2   z = 10^1    y = 4971033
x = 10^2   z = 10^3    y = 4971032
x = 10^4   z = 10^3    y = 2485516
x = 10^8   z = 10^3    y = 1242758
x = 10^16  z = 10^3    y = 621379
x = 10^16  z = OWFL

在这里,z点溢出(10^19 > 2^62-1),计算将继续在Bignum领域,并将计算 x**y。请注意,这里将计算 (10^16)^621379,而且 (10^16) 仍然是54位, 54*621379 是33554466,大于33554432(由34)。因为它越大你就会收到警告,而ruby只会用double计算,因此结果是 Infinity%