= Integer nth root
{title2=$\lfloor n^{1/k}\rfloor$}
For a <nonnegative integer> $N$ and a positive <integer> $k$, the <integer nth root> is the unique <integer> $r\ge0$ such that $r^k\le N<(r+1)^k$. Thus $\lfloor\sqrt[3]{30}\rfloor=3$.
Because $r\mapsto r^k$ 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.
Back to article page