14

有几种方法可以仅使用整数算术来找到整数平方根。比如这个。它带来了有趣的阅读和一个非常有趣的理论，特别是对于我这一代，这些技术不再那么有用了。

最主要的是它不能使用浮点运算，因此排除了牛顿法及其推导。我知道找到根的唯一另一种方法是二项式展开，但这也需要浮点运算。

有哪些技术/算法仅使用整数算术计算整数 n 次根？

编辑：感谢到目前为止的所有答案。他们似乎都在进行稍微聪明的试验和改进。没有更好的办法吗？

Edit2：好的，所以如果没有试验/改进以及牛顿法或二进制搜索，似乎没有聪明的方法可以做到这一点。谁能在理论上对两者进行比较？我在两者之间运行了许多基准测试，发现它们非常相似。

4

6 回答 6

9

您可以仅使用整数算术来使用牛顿法，步骤与浮点算术相同，只是您必须将浮点运算符替换为具有不同运算符的语言中的相应整数运算符。

假设您想找到 的第 k 个整数根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.

于 2012-01-11T21:44:37.643 回答
6

一种明显的方法是将二进制搜索与平方乘幂结合使用。这将允许您找到： 二分查找中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

一种简单的解决方案是使用二进制搜索。

假设我们正在寻找 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 回答
3

在我看来，Shifting nth root 算法提供了你想要的东西：

移位第 n 根算法是一种用于提取正实数的第 n 根的算法，该算法通过从最高有效位开始移位 n 位radicand 迭代地进行，并在每次迭代中产生一位根的数字，以某种方式类似于长除法。

链接的维基百科页面上有工作示例。

于 2012-01-12T09:17:54.807 回答
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 回答