galois.iroot

galois.iroot(n: int, k: int) int

Computes \(x = \lfloor n^{\frac{1}{k}} \rfloor\) such that \(x^k \le n < (x + 1)^k\).

Parameters
n: int

A non-negative integer.

k: int

The positive root \(k\).

Returns

The integer \(k\)-th root of \(n\).

See also

isqrt, ilog

Examples

In [1]: n = 1000

In [2]: x = galois.iroot(n, 5); x
Out[2]: 3

In [3]: print(f"{x**5} <= {n} < {(x + 1)**5}")
243 <= 1000 < 1024

Last update: Mar 30, 2022