Determining which integer is closest to the kth root of n without using floating point arithmetic?

Question

Suppose that I want to compute ^k√n rounded to the nearest integer, where n and k are nonnegative integers. Using binary search, I can find an integer a such that

a^k ≤ n < (a+1)^k.

This means that either a or a+1 is the kth root of n rounded to the nearest integer. However, I'm not sure how to determine which one it is without doing some calculations that involve floating-point arithmetic.

Given the values of a, n, and k, is there a way to determine the kth root of n rounded to the nearest integer without doing any floating-point calculations?

Thanks!

Answer 1

2^ka^k < 2^kn < (2a+1)^k → (dividing by 2^k) a^k < n < (a+0.5)^k → (taking the kth root) a < ^k√n < a+0.5, so the kth root of n is closer to a than to a+1. Note that the edge case will not occur; the kth root of an integer can not be an integer plus 0.5 (a+0.5) as the kth roots of n which are not kth powers are irrational and if n were a perfect kth power, then the kth root would be an integer.

Answer 2

The answers by Ramchandra Apte and Lazarus both contain what seems to be the essence of the correct answer, but both are also (at least to me) a bit hard to follow. Let me try to explain the trick they seem to be getting at, as I understand it, a bit more clearly:

The basic idea is that, to find out whether a or a+1 is closer to ^k√n, we need to test whether ^k√n < a+½.

To get rid of the ½, we can simply multiply both sides of this inequality by 2, giving 2·^k√n < 2a+1, and by raising both sides to the k-th power (and assuming they're both positive) we get the equivalent inequality 2^k·n < (2a+1)^k. So, at least as long as 2^k·n = n &ll; k does not overflow, we can simply compare it with (2a+1)^k to obtain the answer.

In fact, we could simply compute b = ⌊ ^k√(2^k·n) ⌋ to begin with. If b is even, then the closest integer to ^k√n is b / 2; if b is odd, it is (b + 1) / 2. Indeed, we can combine the two cases and say that the closest integer to ^k√n is ⌊ (b+1) / 2 ⌋, or, in pseudo-C:

int round_root( int k, int n ) {
    int b = floor_root( k, n << k );
    return (b + 1) / 2;
}

---

Ps. An alternative approach could be to compute an approximation (a+½)^k directly using the binomial theorem as (a+½)^k = ∑_i=0..k (k choose i) a^k−i / 2ⁱ &approx; a^k + k·a^k−1 / 2 + ... and compare it directly with n. However, at least naïvely, summing all the terms of the binomial expansion would still require keeping track of k extra bits of precision (or at least k−1; I believe the last term can be safely neglected), so it may not gain much over the method suggested above.