galois.isqrt(n: int) → int

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

Info

This function is included for Python versions before 3.8. For Python 3.8 and later, this function calls math.isqrt() from the standard library.

Parameters
n: int

A non-negative integer.

Returns

The integer square root of \(n\).

See also

iroot, ilog

Examples

In [1]: n = 1000

In [2]: x = galois.isqrt(n); x
Out[2]: 31

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