search

Isqrt integer square root of X

Built-in:

var n = 1234
say n.isqrt
say n.iroot(2)

Explicit implementation for the integer k-th root of n:

func rootint(n, k=2) {
    return 0 if (n == 0)
    var (s, v) = (n, k - 1)
    loop {
        var u = ((v*s + (n // s**v)) // k)
        break if (u >= s)
        s = u
    }
    s
}

Implementation of integer square root of n (using the quadratic residue algorithm):

func isqrt(x) { var (q, r) = (1, 0); while (q <= x) { q <<= 2 }
    while (q > 1) { q >>= 2; var t = x-r+q; r >>= 1
        if (t >= 0) { (x, r) = (t, r+q) } } r }

say isqrt.map(0..65).join(' '); printf("\n")

for n in (1..73 `by` 2) {
    printf("isqrt(7^%-2d): %42s\n", n, isqrt(7**n).commify) }

hashtag
Output:

PreviousInverted syntaxNextIterated digits squaring

Last updated