801. The kth Root of a Real Number
Given a non-negative real x and a whole number k, print the real r >= 0 with
r^k = x, to exactly 6 digits after the decimal point.
x = 8.000000, k = 3 -> 2.000000
x = 2.000000, k = 2 -> 1.414214
x = 0.001000, k = 3 -> 0.100000
x = 0.250000, k = 2 -> 0.500000
## Why not pow(x, 1.0 / k)
Because 1.0 / k is itself inexact for most k, and pow is implemented as
exp(y * log(x)), so the result carries the error of a logarithm, a multiplication and an
exponential. At k = 3 and x = 1000000000 the library answer can miss the exact 1000 by
enough to change the sixth decimal. The search below never leaves the original numbers.
Problem 1343 makes the same argument for whole-number roots and fixes it with integer multiplication; this is the real-valued version of that lesson.
## Why the predicate is monotone
For r >= 0 and k >= 1, r^k is non-decreasing in r: multiplying more of a larger
non-negative number cannot give a smaller product. So the answers to "is r^k <= x?" read
YES YES no no, and the answer is the seam.
## The bounds
lo = 0.
hi = max(1, x). Taking hi = x is WRONG whenever x < 1: the square root of 0.25 is
0.5, which is larger than 0.25, and a search stopping at 0.25 would print that instead.
The example list above includes that case for exactly this reason.
## Computing the power
Multiply k times in a loop. With k at most 10 that is ten multiplications, and it stays in
the original units instead of going through logarithms. The intermediate can reach
(10^9)^10 = 10^90, which a double holds comfortably; its top is about 1.8 * 10^308.
## Fixed iterations, never an epsilon
One hundred halvings of an interval that starts at most 10^9 wide leave a gap of about
10^-21, well under what a double can distinguish, and the loop takes the same time on every
input. A while (hi - lo > 1e-9) loop on this range can fail to terminate, because near
10^9 the spacing of doubles is larger than 10^-9 and the interval stops shrinking.
## The boundary that breaks a careless implementation
x = 0. The answer is 0, and a bound of max(1, x) keeps the interval valid; a loop that starts
its power accumulator at x rather than at 1 gets k = 1 wrong as well.
## Width
There is no integer type in this solution at all, which is the point. The running product reaches
10^90, past every fixed-width integer there is, and a double carries it because its exponent
range runs to about 10^308. Reaching for 64 bits here would be the wrong instinct.
## Related problems
Problem 800 is the same search with k = 2 and a variable number of printed digits. Problem 1343
is the whole-number kth root, and problem 802 replaces the pure power with a full cubic.
## Cost
Time O(100 * k). Space O(1).
Constraints - `0 ≤ x ≤ 10^9` - `1 ≤ k ≤ 10` - `x` has at most 6 digits after the decimal point - every answer is at least `10^-9` away from a halfway rounding point at 6 digits
Input
One line containing two values, a real x then a whole number k, separated by a space. x is written in plain decimal form with at most 6 digits after the point.
Output
Print the kth root of x with exactly 6 digits after the decimal point, in plain fixed notation and never in exponent form, alone on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.