Monday, August 31, 2015

LeetCode OJ - Sqrt(x)

Problem:

Please find the problem here.

Solution:

Let's solve the problem using Newton's method, a fairly standard solution.

Newton's method can be used to find zero of functions.


The function is $ f(y) = y^2 - x = 0 $, the function has a zero at $ \sqrt{x} $ and $ -\sqrt{x} $, we will ignore the negative one.


The Newton's iteration is based on an initial estimate of the root, and then iterate as follow:

$ \begin{eqnarray*} x_{n+1} &=& x_n - \frac{f(x_n)}{f'(x_n)} \\ &=& x_n - \frac{x_n^2 - x}{2x_n} \\ &=& x_n - \frac{x_n^2}{2x_n} + \frac{x}{2x_n} \\ &=& x_n - \frac{x_n}{2} + \frac{x}{2x_n} \\ &=& \frac{x_n}{2} + \frac{x}{2x_n} \\ &=& \frac{x_n + \frac{x}{x_n}}{2} \\ \end{eqnarray*} $

Therefore, we can simply implement the equation, but when do we stop?

By doing a simple experiment with the largest possible integer, it takes around 13 iterations to converge to the answer. To play safe, I just run 20 iterations.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/sqrtx/

#include "LEET_SQRTX.h"
#include <stack>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_SQRTX
{
    class Solution
    {
    public:
        
        int mySqrt(int x)
        {
            if (x == 0)
            {
                return 0;
            }
            else if (x < 0)
            {
                throw 1;
            }
            double estimate = 1;
            for (int i = 0; i < 20; i++)
            {
                estimate = (estimate + x / estimate) / 2;
            }
            return (int)estimate;
        }
    };
};

using namespace _LEET_SQRTX;

int LEET_SQRTX()
{
    Solution s;
    cout << s.mySqrt(289) << endl;
    return 0;
}

No comments :

Post a Comment