假设我想计算k√n四舍五入到最近的整数，其中n和k是非负整数。使用二进制搜索，我可以找到一个整数a，这样
ak≤n<(a+1)k。
这意味着a或a+1是n的第k个根，四舍五入到最接近的整数。然而，如果不进行一些涉及浮点运算的计算，我不知道如何确定它是哪一个。
给定a、n和k的值，是否有一种方法可以在不进行任何浮点计算的情况下确定四舍五入到最近整数的n的第k个根？
谢谢！
2kak<2kn<(2a+1)k→(除以2k)ak<n<(a+0.5)k→(取第k个根)a<k√n<a+0.5，因此n的第k个根比a+1更接近a。请注意，边缘情况不会发生；整数的第k根不能是整数加0.5(a+0.5)，因为不是第k次幂的n的第k个根是无理的，并且如果n是完美的第k次方，那么第k个根将是整数。
Ramchandra Apte和Lazarus的答案都包含了正确答案的本质，但两者(至少对我来说)都有点难以理解。让我试着更清楚地解释一下他们似乎在耍的把戏，正如我所理解的：
基本思想是，为了找出a或a+1是否更接近k√n，我们需要测试k√n<a+½。
为了摆脱½，我们可以简单地将这个不等式的两边乘以2，得到2·k√n<2a+1，并且通过将两边提升到k的次幂(并且假设它们都是正的)，我们得到等价不等式2k·n<(2a+1)k。所以，至少只要2k·n=n&llk不溢出，我们可以简单地将其与(2a+1)k进行比较以获得答案。
事实上，我们可以简单地计算b=⌊k√(2k·n)⌋首先。如果b是偶数，则与k√n最接近的整数为b/2；如果b是奇数，则为(b+1)/2。事实上，我们可以将这两种情况结合起来，说最接近k√n的整数是⌊(b+1)/2⌋，或者，在伪C中：
int round_root( int k, int n ) {
int b = floor_root( k, n << k );
return (b + 1) / 2;
}
Ps。另一种方法可以是直接使用二项式定理计算近似值(a+½)k(a+½)k=∑i=0.k(k选择i)ak−i/2i近似值ak+k&中点ak−1/2+。。。并与n直接比较。然而，至少在天真的情况下，对二项式展开的所有项求和仍然需要跟踪k额外的精度位(或者至少k−1；我相信最后一项可以安全地忽略)，因此它可能不会比上面建议的方法获得太多好处。
我的猜测是，您希望在FPGA/CPLD或资源有限的处理器上使用此算法，因为您的方法让我想起了CORDIC。因此，我将提出一个考虑到这一点的解决方案。
当你到达a^k ≤ n < (a+1)^k时，这意味着x=根(n，k)的底是"a"。换句话说，x＝a+f，其中0=<f<0.5。因此，将等式乘以2，就会得到2x=2a+2f。它基本上意味着CCD_ 6(由于2f<1)。现在，x = √n (kth root)，因此2x = k√((2^k)*n) (kth root)。所以，只需将n向左移动k位，然后用你的算法计算它的第k个根。如果它的下界恰好是n的第k根的2倍，那么n的第K根是a，否则它是a+1。
假设你有一个函数，它给出了n的第k个根(rootk(n))的下界，那么使用二进制运算符和C符号的最终结果将是：
closestage＝a+((rootk(n)<lt；1) ==rootk(n>>k))；
计算(a + 0.5)*10的立方体(或10a + 5-无浮点运算)，然后将其除以1000。
然后检查号码在哪一边。
乘以10的想法是将小数点向右移动一个位置。然后我们除以1000，因为我们乘以10 3倍，因为立方。
例如：
Input: 16
a = 2
a+1 = 3
a^3 = 8
(a+1)^3 = 27
10a + 5 = 25
25^3 = 15625
floor(15625 / 1000) = 15
16 > 15, thus 3 is closer.
正如Oli所指出的，它还可以计算(a + 0.5)*2(或2a + 1)的立方体，然后将其除以8。
例如：
2a + 1 = 5
5^3 = 125
floor(125 / 8) = 15
16 > 15, thus 3 is closer.
您可以使用牛顿方法来查找a；它能很好地处理整数，并且比二进制搜索更快。然后使用平方和乘幂算法计算ak和(a+1)k。这里有一些代码，在Scheme中，因为我碰巧有它：
(define (iroot k n) ; largest integer x such that x ^ k <= n
(let ((k-1 (- k 1)))
(let loop ((u n) (s (+ n 1)))
(if (<= s u) s
(loop (quotient (+ (* k-1 u) (quotient n (expt u k-1))) k) u)))))
(define (ipow b e) ; b^e
(if (= e 0) 1
(let loop ((s b) (i e) (a 1)) ; a * s^i = b^e
(let ((a (if (odd? i) (* a s) a)) (i (quotient i 2)))
(if (zero? i) a (loop (* s s) i a))))))
要确定ak和(a+1)k中哪一个更接近根，可以使用幂算法计算(a+1/2)k—这是平方和乘法运算可以执行的精确计算—然后将结果与n进行比较，并确定哪一侧更接近。
编辑：-
很抱歉误解了这个问题。以下是原始问题的可能解决方案：-
使用牛顿近似定理：-
here = means (approximately = )
f(b+a) = f(b) + a*f'(b)
a -> 0
f(x) = x^k
f'(x) = k*x^(k-1)
hence using above equation
f(a+0.5) = a^k + 1/2*k*a^(k-1);
need to check n < f(a+0.5)
n < a^k + 1/2*k*a^(k-1)
rearranging (n-a^k)*2 < k*a^(k-1)
注意：您可以使用二项式定理来获得更高的精度。
思考。理想情况下，你应该再做一步二进制搜索，看看a+½的根在哪一边。也就是说，检验不等式
(a+0.5)k<n
但是左手边很难精确计算(浮点问题)。所以写下一个等价的不等式，其中所有的项都是整数：
(2a+1)k<2kn
完成。