public int sqrt3(int x) { // newton's method
        if(x == 0) return 0;
        // f(t) = t^2 - x; f'(t) = 2t;
        // t' = t - f(t) / f'(t) = t - (t^2 - x) / 2t = (t + x / t) / 2;
        // t' = (t + x / t) / 2
		double t = 1.0;
		double former = 0.0;
		while(t!=former){
			former = t;
            // t + x/t gets min when t = sqrt(x)
            // then min(t+x/t) = 2*sqrt(x)
            // thus 2*t'=t+x/t gets converged from the right side rather than the left side
            // so we always have t' >= sqrt(x)
			t = (t + x / t) / 2;
            System.out.println(t + "\t" + former);
        }
        return (int)t;
    }