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.
An integer root bound brackets an integer nth root using exact inequalities. If has bit length and , then
Indeed, ; taking positive real th roots gives the bounds. They supply an initial interval for binary search.
For and , the bit length is ten, giving . Testing nearby powers then finds the exact value . Using inequalities rather than rounded roots avoids excluding a perfect power at a search boundary.

Articles by others on the same topic (0)

There are currently no matching articles.