爲什麼10^9942066可以計算出沒有溢出的最大功率？

Question

在紅寶石中，一些大的數字大於無窮大。通過二進制搜索，我發現：

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

這是爲什麼？ 10 有什麼特別之處？它似乎不是像9999999那樣的任意數字，它不接近任何兩個冪（它近似等於2 ^{33026828.36662442}）。

爲什麼紅寶石的無限無窮？如何參與10 ？

---

我現在意識到，任何數量超過10 更大會溢出到無限遠：

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

但是仍然留下了一個問題：爲什麼10 ？

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是紅寶石的內部限制其被用作一個常數檢查一個功率計算將是過大或沒有，並且被定義爲32*1024*1024。 base是10，並且n是仍然適合Fixnum的底座的最大功率指數。

不幸的是，由於用於計算大數字的冪的算法，我無法找到比這個近似值更好的方法，但如果您的代碼需要在執行前檢查有效性，那麼它可能已經足夠用作上限值大數取冪。

---

原題：

的問題不在於9942066，但與你的號碼中的一個是整數，另外一個是浮動。因此，

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

第一個可以用一個特定的數字來表示，它小於Infinity。第二個，因爲它仍然是一個浮動不能代表一個實際的數字，只是取代Infinity，這當然不大於Infinity。

更新問題：

你是正確的，似乎有大約9942066差一些（如果你使用的是Linux下一個64位的紅寶石，作爲限制可能是在其他系統不同）。雖然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（比系統比特大小小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），極限之後，紅寶石不會做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），計算將繼續碧gnum領域，並且會計算x**y。注意這裏它會計算(10^16)^621379，而(10^16)仍然是54位，54*621379是33554466，它大於33554432（34）。因爲它更大，你會得到警告，紅寶石只會用雙計算，因此結果是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位（紅寶石的Fixnums可以存儲比機器大小限制小兩位的值）。

對於12^16我們可以很容易地確定截斷值。它將是32*1024*1024/ceil(log2(12^16))，即33554432/58 ~= 578525。我們可以很容易地在紅寶石現在檢查：

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。如果您在紅寶石檢查，值實際上是相當接近這個數字：

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 

Answer 2

注意，問題不在於數量，但與操作，通過你得到警告的說。

$ ruby -e 'puts (1.0/0) > 10**9942067' 
-e:1: warning: in a**b, b may be too big 
false 

問題是10**9942067打破了Ruby的冪函數。不是拋出異常，這會是一種更好的行爲，而是錯誤地導致無窮大。

$ ruby -e 'puts 10**9942067' 
-e:1: warning: in a**b, b may be too big 
Infinity 

The other answer explains why this happens near 10e9942067。

10**9942067不大於無窮大，它錯誤地導致無窮大。這是很多數學圖書館的一個壞習慣，這使得數學家們沮喪地把他們的眼球弄出來。

無窮大不大於無窮大，它們是平等的，所以你的大於檢查是錯誤的。你可以通過檢查它們是否相等來看到這一點。

$ ruby -e 'puts (1.0/0) == 10**9942067' 
-e:1: warning: in a**b, b may be too big 
true 

將此與直接使用科學記數法指定數字對比。現在Ruby不需要對數字進行數學計算，它只是知道任何實數都小於無窮大。

$ ruby -e 'puts (1.0/0) > 10e9942067' 
false 

現在，您可以隨心所欲地放大指數。

$ ruby -e 'puts (1.0/0) > 10e994206700000000000000000000000000000000' 
false