#include <math.h>
typedef unsigned long long ULONG;

class Solution {
public:
    int sqrt_newton(int x) {
        if (x==0) return x;
        double dividend = x;
        double val = x;
        double last;
        do {
            last = val;
            val = (val + dividend / val) * 0.5;
        } while(abs(val - last) > 1e-9); // precision
        return (int)val;
    }
}