使用整数算术计算第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个根

回答

相关问题