class Solution {
public:
int mySqrt(int x) {
double guess = 4;
double epsilon = 1e4;
while (abs(guess * guess  x) > epsilon) {
guess = (guess + x/guess) / 2;
}
return guess;
}
};
Newton Method, simple and clean

+1, but you don't need to use such a low tolerance. You can also remove abs() if you start from the righthand side of the root; since the function is convex the iterates are decreasing.
class Solution { public: int mySqrt (int x) { if (x == 0) { return 0; } if (x < 0) { return 1; } // Fail on negatives // Margin of error for safety static constexpr double margin = 1e4; // Initial guess double y = x; // Newton's method double yold, diff; do { yold = y; y = (y*y + x) / 2 / y; diff = yold  y; } while (diff > 0.5  margin); return y; } };