For a nonnegative integer and a positive integer , the integer nth root is the unique integer such that . Thus .
Because is increasing on the nonnegative integers, binary search with exact comparisons computes the root without relying on rounded floating-point arithmetic. This is useful in perfect-power tests and exact bounds in integer factorization. Verifying the two inequalities also certifies an answer obtained from an approximate initial guess.
New to topics? Read the docs here!