Integer root bound (source code)

= Integer root bound

An <integer root bound> brackets an <integer nth root> using exact inequalities. If $N>0$ has <bit length> $\ell$ and $k\ge1$, then
$$
2^{\lfloor(\ell-1)/k\rfloor}\le\lfloor N^{1/k}\rfloor<2^{\lceil\ell/k\rceil}.
$$
Indeed, $2^{\ell-1}\le N<2^\ell$; taking positive real $k$th roots gives the bounds. They supply an initial interval for <binary search>.

For $N=1000$ and $k=3$, the <bit length> is ten, giving $8\le\lfloor\sqrt[3]{1000}\rfloor<16$. Testing nearby powers then finds the exact value $10$. Using inequalities rather than rounded roots avoids excluding a perfect power at a search boundary.