## Monday, August 31, 2015

### LeetCode OJ - Sqrt(x)

Problem:

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;
}