Issue 9762 - std.math.isqrt
Summary: std.math.isqrt
Status: NEW
Alias: None
Product: D
Classification: Unclassified
Component: phobos (show other issues)
Version: D2
Hardware: All All
: P4 enhancement
Assignee: No Owner
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2013-03-19 15:56 UTC by bearophile_hugs
Modified: 2024-12-01 16:17 UTC (History)
0 users

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this issue.
Description bearophile_hugs 2013-03-19 15:56:44 UTC
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
Comment 1 bearophile_hugs 2014-08-24 16:10:00 UTC
See also Issue 13369
Comment 2 dlangBugzillaToGithub 2024-12-01 16:17:02 UTC
THIS ISSUE HAS BEEN MOVED TO GITHUB

https://github.com/dlang/phobos/issues/9601

DO NOT COMMENT HERE ANYMORE, NOBODY WILL SEE IT, THIS ISSUE HAS BEEN MOVED TO GITHUB