Newton Method, simple and clean


  • 1
    N
    class Solution {
    public:
        int mySqrt(int x) {
            double guess = 4;
            double epsilon = 1e-4;
            while (abs(guess * guess - x) > epsilon) {
                guess = (guess + x/guess) / 2;
            }
            return guess;
        }
    };

  • 0
    P

    +1, but you don't need to use such a low tolerance. You can also remove abs() if you start from the right-hand 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 = 1e-4;
            
            // 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;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.