在不使用浮点运算的情况下确定哪个整数最接近n的第k个根？

Question

假设我想计算^ķ √N四舍五入到最接近的整数,其中n和k为非负整数.使用二进制搜索,我可以找到一个这样的整数

一个^ķ ≤Ñ<(A + 1)^ķ.

这意味着a或a + 1是n的第k个根,四舍五入到最接近的整数.但是,我不知道如何在不进行涉及浮点运算的计算的情况下确定它是哪一个.

给定a,n和k的值,有没有办法确定n的第k个根四舍五入到最接近的整数而不进行任何浮点计算？

谢谢!

Answer 1

2 ^ķ一个^ķ <2 ^ķ Ñ<(2A + 1)^ķ →(除以2 ^ķ一个)^ķ <N <(A + 0.5)^ķ →(以第k根)一个< ^ķ √N<A + 0.5,因此n的第k根更接近a比a+1.请注意,边缘情况不会发生; 整数的第k个根不能是整数加0.5(a + 0.5),因为不是第k个幂的n的第k个根是无理的,如果n是完全的第k个幂,那么第k个根将是整数.