Integer nth root Created 2026-10-20 Updated 2026-11-05
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.
Integer root bound Created 2026-10-20 Updated 2026-11-05
An integer root bound brackets an integer nth root using exact inequalities. If has bit length and , thenIndeed, ; 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.