14

整数演算のみを使用して整数の平方根を求める方法はいくつかあります。たとえば、これ。これは興味深い読み物であり、非常に興味深い理論でもあります。特に、そのような手法があまり役に立たなくなった私の世代にとってはそうです。

主なことは、浮動小数点演算を使用できないため、newtons メソッドとその派生を除外することです。根を見つけるために私が知っている他の唯一の方法は二項展開ですが、それには浮動小数点演算も必要です。

整数演算のみを使用して整数 n 乗根を計算するための手法/アルゴリズムは何ですか?

編集：これまでのすべての回答に感謝します。それらはすべて、もう少し知的な試行錯誤のようです。もっと良い方法はありませんか？

Edit2:わかりましたので、試行/改善と、ニュートン法またはバイナリ検索なしでこれを行うスマートな方法はないようです。理論的に2つの比較を提供できる人はいますか? この 2 つのベンチマークを何度も実行したところ、非常によく似ていることがわかりました。

4

6 に答える 6

9

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

の整数 k 乗根を見つけたいとしましょう。これは、 のようなa > 0最大の整数でなければなりません。任意の正の整数から開始します (もちろん、適切な開始点が役立ちます)。rr^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-11T21:44:37.643 に答える
6

明らかな方法の 1 つは、2 乗によるべき乗と一緒に二分探索を使用することです。これにより、以下を見つけることができます。場合によっては、検索をに減らします。そうでない場合は、検索を に減らします。nthRoot(x, n)O(log (x + n))[0, x]kk^n <= xkk^n <= x[k + 1, x][0, k]

よりスマートまたは高速なものが必要ですか?

于 2012-01-11T21:51:20.613 に答える
3

Shifting nth root アルゴリズムはまさにあなたが望むものを提供するように私には思えます:

シフト n 乗根アルゴリズムは、正の実数の n 乗根を抽出するためのアルゴリズムであり、最上位から開始して基数の n 桁をシフトすることによって反復的に進行し、各反復で根の 1 桁を次のように生成します。長割りに似ています。

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

于 2012-01-12T09:17:54.807 に答える
3

簡単な解決策の 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)
于 2012-01-11T21:51:05.117 に答える
1

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

コードをコピーして 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
于 2019-05-21T01:23:29.150 に答える
0

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-03T00:58:05.700 に答える