为什么10 ^ 9942066是我可以在没有溢出的情况下计算的最大功率？

Question

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

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

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

为什么红宝石的无限无限？10 ^9942066如何参与？

---

我现在意识到,任何大于10 ^{9942066的数字}都会溢出到无穷大:

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

但这仍然留下了一个问题:为什么10 ^9942066？

Answer 1

TL; DR

我没有内部完成的计算numeric.c的int_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*1024.base是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)) == 54),54*621378是33554412.这只是略小于33554432(20),之后ruby不会做Bignum取幂的极限,而只是转换y为double,并希望最好(这显然会失败,并且刚回来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.

请注意,只有在使用电源功能时才会执行这些检查.这就是为什么你仍然可以这样做(10**9942066)*10,因为在进行简单乘法时不存在类似的检查,这意味着你可以在ruby中实现自己的快速取幂方法,在这种情况下它仍然可以使用更大的值,尽管你不会进行这种安全检查了.例如,参见这个快速实现:

def unbounded_pow(x,n)
  if n < 0
    x = 1.0 / x
    n = -n
  end
  return 1 if n == 0
  y = 1
  while n > 1
    if n.even?
      x = x*x
      n = n/2
    else
      y = x*y
      x = x*x
      n = (n-1)/2
    end
  end
  x*y
end

puts (10**9942066) == (unbounded_pow(10,9942066)) # => true
puts (10**9942067) == (unbounded_pow(10,9942067)) # => false 
puts ((10**9942066)*10) == (unbounded_pow(10,9942067)) # => true

但我怎么知道特定基地的截止值？

我的数学并不是很好,但我可以告诉一种方法来估算截止值的位置.如果检查上述调用,您可以看到Fixnum和Bignum之间的转换发生在中间基数达到Fixnum的限制时.此阶段的中间基数将始终具有2的幂的指数,因此您只需最大化此值.例如,让我们试着找出12的最大截止值.

首先,我们必须检查我们可以在Fixnum中存储的最高基数:

ceil(log2(12^1)) = 4
ceil(log2(12^2)) = 8
ceil(log2(12^4)) = 15
ceil(log2(12^8)) = 29
ceil(log2(12^16)) = 58
ceil(log2(12^32)) = 115

我们可以看到12^16我们可以存储的最大值为62位,或者如果我们使用的是32位机器,12^8则可以容纳30位(ruby的Fixnums可以存储的值最多比机器大小限制小两位).

因为12^16我们可以很容易地确定截止值.它将是32*1024*1024 / ceil(log2(12^16)),是33554432 / 58 ~= 578525.我们现在可以在ruby中轻松检查:

irb(main):004:0> ((12**16)**578525).class
=> Bignum
irb(main):005:0> ((12**16)**578526).class
(irb):5: warning: in a**b, b may be too big
=> Float

现在我们讨厌回到原来的基地12.在那里截止将是578525*16(16是新基地的指数),这是9256400.如果您签入ruby,则值实际上非常接近此数字:

irb(main):009:0> (12**9256401).class
=> Bignum
irb(main):010:0> (12**9256402).class
(irb):10: warning: in a**b, b may be too big
=> Float