Comment #0 by bearophile_hugs — 2013-03-19T15:56:44Z
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 by bearophile_hugs — 2014-08-24T16:10:00Z
See also Issue 13369
Comment #2 by robert.schadek — 2024-12-01T16:17:02Z