[Issue 9762] New: std.math.isqrt

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=9762

           Summary: std.math.isqrt
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody at puremagic.com
        ReportedBy: bearophile_hugs at eml.cc


--- Comment #0 from bearophile_hugs at eml.cc 2013-03-19 15:56:44 PDT ---
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

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------