Quite a few people used Newton already, but I didn't see someone make it this short. Same solution in every language. Explanation under the solutions.

**C++ and C**

```
long r = x;
while (r*r > x)
r = (r + x/r) / 2;
return r;
```

**Python**

```
r = x
while r*r > x:
r = (r + x/r) / 2
return r
```

**Ruby**

```
r = x
r = (r + x/r) / 2 while r*r > x
r
```

**Java and C#**

```
long r = x;
while (r*r > x)
r = (r + x/r) / 2;
return (int) r;
```

**JavaScript**

```
r = x;
while (r*r > x)
r = ((r + x/r) / 2) | 0;
return r;
```

**Explanation**

Apparently, using only integer division for the Newton method works. And I guessed that if I start at x, the root candidate will decrease monotonically and never get too small.

The above solutions all got accepted, and in C++ I also verified it locally on my PC for all possible inputs (0 to 2147483647):

```
#include <iostream>
#include <climits>
using namespace std;
int mySqrt(int x) {
long long r = x;
while (r*r > x)
r = (r + x/r) / 2;
return r;
}
int main() {
for (long long x=0; x<=INT_MAX; ++x) {
long long r = mySqrt(x);
if (r<0 || r*r > x || (r+1)*(r+1) <= x)
cout << "false: " << x << " " << r << endl;
if (x % 10000000 == 0)
cout << x << endl;
}
cout << "all checked" << endl;
}
```