std.math.isqrt

[dlangBugzillaToGithub]

bearophile_hugs reported this on 2013-03-19T15:56:44Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=9762

Description

Consider adding a std.math.isqrt function for integral square roots (this works with BigInt too). A simple implementation:


T isqrt(T)(T x) /*pure nothrow*/
in {
    assert(x > 0);
} body {
    static T abs(T)(T x) /*pure nothrow*/ {
        return x >= 0 ? x : -x;
    }

    static T next(T n, T i) /*pure nothrow*/ {
        return (n + i / n) >> 1;
    }

    T one = 1;
    auto n = one;
    auto n1 = next(n, x);

    while (abs(n1 - n) > one) {
        n = n1;
        n1 = next(n, x);
    }

    while (n1 * n1 > x)
      n1 -= one;
    return n1;
}


void main() {
    import std.stdio, std.bigint;
    writeln(isqrt(1024 * 1024));
    writeln(isqrt(1024 * 1023));
    writeln(isqrt(BigInt(1024 * 1024)));
    writeln(isqrt(BigInt(1024 * 1023)));
}



Use cases: in a Sieve of Eratosthenes and other numeric algorithms.

Sometimes this is not enough:
cast(uint)sqrt(n)

See also:
http://en.wikipedia.org/wiki/Integer_square_root

[dlangBugzillaToGithub]

bearophile_hugs commented on 2014-08-24T16:10:00Z

See also Issue 13369