使用整數算術計算第N個根

有幾種方法只使用整數算術來查找整數平方根。例如this one。它使有趣的閱讀和一個非常有趣的理論，特別是對於我這一代，這種技術不再那麼有用。使用整數算術計算第N個根

最主要的是它不能使用浮點運算，因此排除了牛頓方法和它的派生。我知道找到根的唯一方法是二項式擴展，但這也需要浮點算術。

有什麼技術/算法用於僅使用整數算術來計算整數n階根？

編輯：感謝所有迄今爲止的答案。他們似乎都稍微有點聰明的試驗和改進。有沒有更好的辦法？

編輯2：好的，所以似乎沒有智能的方法來做到這一點沒有試驗/改進和牛頓法或二分法搜索。任何人都可以在理論上提供兩個的比較？我在兩者之間運行了許多基準，並發現它們非常相似。

來源

2012-01-11 Matt

什麼是您所需的輸入值範圍？ – 2012-01-11 21:27:22

@PaulR，理想情況下它可以是可擴展的，但我認爲你現在可以假設基數和數字都是32位（無符號）整數。 – Matt 2012-01-11 21:32:19

你允許哪種整數操作？平方根是一種特殊情況，因爲可以使用加法，減法和移位來提取它們。 – Neil 2012-01-11 21:39:59

您可以使用牛頓的方法只使用整數算術，其步驟與浮點算術相同，但您必須用具有不同運算符的語言中的相應整數運算符替換浮點運算符。

假設您想要找到a > 0的整數第k個根，它應該是最大的整數r，例如r^k <= a。你從任何正整數開始（當然，一個好的起點有幫助）。

int_type step(int_type k, int_type a, int_type x) { 
    return ((k-1)*x + a/x^(k-1))/k; 
} 

int_type root(int_type k, int_type a) { 
    int_type x = 1, y = step(k,a,x); 
    do { 
     x = y; 
     y = step(k,a,x); 
    }while(y < x); 
    return x; 
}

除了第一步，你有x == r <==> step(k,a,x) >= x。

來源

2012-01-11 21:44:37

再次看過牛頓拉夫森後，我發現有一種方法可以做到這一點，但它經常到達兩個數字之間翻轉的點（例如3到4之間的15個翻轉的平方根）。爲了應對這種情況的完整的解決方案是[這裏]（http://pastebin.com/3UbgNMHG） – Matt 2012-01-11 22:27:27

對於平方根，它翻轉正是''正1'和'N'之間= N * N-1' 。我不確定是否有更高的能力會導致翻轉，但是如果步驟增加了對根的近似值 - 除了第一步，如果起點小於目標 - 就完成了，較小的值是整數根。 – 2012-01-11 22:35:33

這與我達成的結論是一樣的，這就是爲什麼我到達上面評論中發佈的代碼。無論基數是什麼，翻轉的值似乎總是高於和低於根，所以根在兩個數之間（因此爲什麼會翻轉）我的代碼處理這個問題。 – Matt 2012-01-12 08:01:09

一個簡單的解決方案是使用二進制搜索。

假設我們找到x的第n個根。

Function GetRange(x,n): 
    y=1 
    While y^n < x: 
     y*2 
    return (y/2,y) 

Function BinSearch(a,b,x,): 
    if a == b+1: 
     if x-a^n < b^n - x: 
      return a 
     else: 
      return b 
    c = (a+b)/2 
    if n< c^n: 
     return BinSearch(a,c,x,n) 
    else: 
     return BinSearch(c,b,x,n) 

a,b = GetRange(x,n) 
print BinSearch(a,b,x,n)

===更快的版本===

Function BinSearch(a,b,x,): 
    w1 = x-a^n 
    w2 = b^n - x 
    if a <= b+1: 
     if w1 < w2: 
      return a 
     else: 
      return b 
    c = (w2*a+w1*b)/(w1+w2) 
    if n< c^n: 
     return BinSearch(a,c,x,n) 
    else: 
     return BinSearch(c,b,x,n)

來源

2012-01-11 21:51:05 ElKamina

一個顯而易見的方法是用exponentiation by squaring一起使用binary search。這將允許您在O(log (x + n))中找到nthRoot(x, n)：在[0, x]中的二進制搜索爲最大整數k，例如k^n <= x。對於一些k，如果k^n <= x，則將搜索減少到[k + 1, x]，否則將其減小到[0, k]。

你需要更聰明還是更快的東西？

來源

2012-01-11 21:51:20 IVlad

我有興趣看看是否有任何方法不涉及試驗改進。儘管通過平方的指數是一個很好的找到的感謝， – Matt 2012-01-12 08:04:36

在我看來，該Shifting nth root algorithm提供你想要什麼：

換擋n次方根算法來提取由n個數字移反覆進行正實數的n次方根的算法這個radicand從最重要的開始，並且在每次迭代時產生一個數字的根，類似於長分區。

有工作鏈接的維基百科頁面上的例子。

來源

2012-01-12 09:17:54 AakashM

從維基百科頁面：「當基數大於radicand時，算法退化爲二分搜索」。我會看看是否有可能使用（有效）十六進制而不是二進制來改進算法。 – Matt 2012-01-13 16:01:54

算法更簡單的VBA。

Public Function RootNth(radicand As Double, degree As Long) As Double 
    Dim countDigits As Long, digit As Long, potency As Double 
    Dim minDigit As Long, maxDigit As Long, partialRadicand As String 
    Dim totalRadicand As String, remainder As Double 

    radicand = Int(radicand) 
    degree = Abs(degree) 
    RootNth = 0 
    partialRadicand = "" 
    totalRadicand = CStr(radicand) 
    countDigits = Len(totalRadicand) Mod degree 
    countDigits = IIf(countDigits = 0, degree, countDigits) 
    Do While totalRadicand <> "" 
    partialRadicand = partialRadicand + Left(totalRadicand, countDigits) 
    totalRadicand = Mid(totalRadicand, countDigits + 1) 
    countDigits = degree 
    minDigit = 0 
    maxDigit = 9 
    Do While minDigit <= maxDigit 
     digit = Int((minDigit + maxDigit)/2) 
     potency = (RootNth * 10 + digit)^degree 
     If potency = Val(partialRadicand) Then 
      maxDigit = digit 
      Exit Do 
     End If 
     If potency < Val(partialRadicand) Then 
      minDigit = digit + 1 
     Else 
      maxDigit = digit - 1 
     End If 
    Loop 
    RootNth = RootNth * 10 + maxDigit 
    Loop 
    End Function

來源

2015-02-03 00:58:05

「比什麼更簡單」？ – 2015-02-03 01:20:49

使用整數算術計算第N個根

回答

相關問題