整数算術でnthルートを計算します

StackOverflow https://stackoverflow.com/questions/8826822

質問

整数算術のみを使用して、整数四角根を見つける方法はいくつかあります。例えば これです. 。それは興味深い読書と非常に興味深い理論にもなります。特に、そのようなテクニックがそれほど有用ではない私の世代にとっても。

主なことは、フローティングポイント算術を使用できないため、Newtonsメソッドを排除し、派生物です。私が根を見つけるために知っている他の方法は二項膨張ですが、それはまた、浮動小数点算術も必要です。

整数算術のみを使用して、積分nのルートを計算するために、どのような手法/アルゴリズムがありますか？

編集：これまでのすべての答えをありがとう。それらはすべて、少しインテリジェントな試験と改善のようです。良い方法はありませんか？

edit2：わかりました。そのため、試用/改善なしでこれを行う賢明な方法はないように思われます。誰でも2つの比較を提供できますか 理論的には？私は2つの間で多くのベンチマークを実行しており、それらが非常に似ていることがわかりました。

役に立ちましたか？

解決

整数算術のみを使用してニュートンの方法を使用できます。ステップは、フローティングポイント演算子を、これらの異なる演算子を持つ言語の対応する整数演算子に置き換える必要がある場合を除き、フローティングポイント算術の場合と同じです。

の整数k-rootを見つけたいとしましょう a > 0, 、これは最大の整数でなければなりません 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.

他のヒント

明らかな方法の1つは、使用することです バイナリ検索 一緒に 二乗による指数. 。これにより、見つけることができます nthRoot(x, n) の O(log (x + n)): ：バイナリ検索イン [0, x] 最大の整数の場合 k そのような k^n <= x. 。いくつかのための k, 、 もしも k^n <= x, 、検索を減らします [k + 1, x], 、そうでなければそれを減らします [0, k].

より賢いものやより速いものが必要ですか？

私には NTHルートアルゴリズムのシフト あなたが望むものを正確に提供します：

シフトn番目のルートアルゴリズムは、最も重要なものから始まり、各反復でルートの1桁を生成することにより、繰り返し進行する正の実数のn番目のルートを抽出するためのアルゴリズムです。長い分裂に似ています。

リンクされたウィキペディアのページには作業例があります。

簡単な解決策の1つは、バイナリ検索を使用することです。

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)

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

アルゴリズムを作成しました VBA の Excel. 。今のところ、整数の根だけを計算します。小数も簡単に実装できます。

コードをコピーしてExcelモジュールに貼り付け、関数の名前をあるセルに入力して、パラメーターを渡すだけです。

Public Function RootShift(ByVal radicand As Double, degree As Long, Optional ByRef remainder As Double = 0) As Double

   Dim fullRadicand As String, partialRadicand As String, missingZeroes As Long, digit As Long

   Dim minimalPotency As Double, minimalRemainder As Double, potency As Double

   radicand = Int(radicand)

   degree = Abs(degree)

   fullRadicand = CStr(radicand)

   missingZeroes = degree - Len(fullRadicand) Mod degree

   If missingZeroes < degree Then

      fullRadicand = String(missingZeroes, "0") + fullRadicand

   End If

   remainder = 0

   RootShift = 0

   Do While fullRadicand <> ""

      partialRadicand = Left(fullRadicand, degree)

      fullRadicand = Mid(fullRadicand, degree + 1)

      minimalPotency = (RootShift * 10) ^ degree

      minimalRemainder = remainder * 10 ^ degree + Val(partialRadicand)

      For digit = 9 To 0 Step -1

          potency = (RootShift * 10 + digit) ^ degree - minimalPotency

          If potency <= minimalRemainder Then

             Exit For

          End If

      Next

      RootShift = RootShift * 10 + digit

      remainder = minimalRemainder - potency

   Loop

End Function
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top