大數的立方根

我想確定大數的立方根。我發現這對較小的數字，但不是在這種情況下的解決方案：大數的立方根

require 'openssl' 
q = OpenSSL::BN::generate_prime(2048) 
ti = q.to_i  #=> 3202718747... 
ti3 = ti ** 3  #=> 328515909... 
m = ti3 ** (1/3.0) #=> Infinity

我希望看到m =的ti原始輸出。是的，這是Matasano挑戰的一部分。到目前爲止，我已經付出了很多努力不去尋求幫助，但是我已經達到了一個要求，那就是「我該如何做一些簡單的事情，在Ruby中」。任何援助讚賞。

來源

2014-08-29 technion

我不知道Matasano的挑戰是什麼，但想到什麼是Newton's Method

上Cube Roots維基百科頁面還建議使用牛頓法

來源

2014-08-29 03:30:36 Dbz

感謝。這看起來像更多的代碼，我希望有一個單一的 - 但如果它的工作，它的作品。我會看看我能否成功實施它。 – technion 2014-08-29 03:36:03

你可以把它擠成幾條線。它看起來比它更復雜！ – Dbz 2014-08-29 03:44:24

是的 - 這是做到了。 – technion 2014-08-29 05:46:49

在紅寶石操作對整數自動提升爲大數（任意精度整數），所以你永遠不會發生溢出。

浮點運算也是如此：你最終得到無窮大，因爲提升到1/3是浮點運算，它所做的第一件事就是嘗試將你的數字轉換爲浮點數。紅寶石浮動的最大數字可以表示大約10^308，而您的數字大概在10^1800左右，所以它會保留並返回Infinity

Ruby對此有一個BigDecimal類。因此，你可能會嘗試做

BigDecimal.new(ti3) ** (1/3.0)

這給出了一個完全錯誤的答案，我 - 我懷疑是因爲（1/3.0）是一個浮動，所以只有大約1/3

BigDecimal.new(ti3) ** Rational(1,3)

在另一隻手爲我產生正確的結果（可忽略的錯誤）。 Rational是Ruby用於精確表示分數的類。在紅寶石2.1可以縮短這

BigDecimal.new(ti3) ** (1r/3)

該文檔不說，僅整數指數的支持，但是這似乎是一個宿醉從紅寶石1.8天

來源

2014-08-29 07:00:18

你是絕對正確的，在發佈之前我確實嘗試了其中的幾個選項。 – technion 2014-08-30 10:05:49

下面的代碼，提出基礎上，給出了兩條建議。

def nthroot(n, a, precision = 1e-1024) 
    x = a 
    begin 
    prev = x 
    x = ((n - 1) * prev + a/(prev ** (n - 1)))/n 
    end while (prev - x).abs > precision 
x 
end

它是基於牛頓方法的實現處理浮點數，但也只是返回無窮大。此版本僅處理整數，但適用於大整數。

當然，一個nthroot，可能被稱爲n = 3。

來源

2014-08-30 10:08:27 technion

大數的立方根

回答

相關問題