# 【LeetCode】 69. Sqrt(x)

## Description
> Implement `int sqrt(int x)`.

> Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

> Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

> 實作 `int sqrt(int x)`。

> 計算並回傳 x 的平方根，x是非負整數。

> 因為回傳的型態是一個整數，小數點之後的部分請全部捨去，只留下並回傳整數部分。

## Example:

Example 1:

Input: 4
Output: 2


Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

## Solution

* 這題我使用[牛頓逼近法](https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A1%BF%E6%B3%95)去實作。
* $x_{n+1} = x_n + \frac{f(x)}{f'(x)}$
* 去找$f(x) = x^2-a=0$的答案。
* 為了精度問題我使用`double`去處理。
* `0`的時候會出問題，要特別處理。
* 捨去小數點使用`floor()`即可。

### Code

class Solution {
public:
    int mySqrt(int x) {
//      x1 = x0 - f(x)/f'(x)
//      f(x) = x^2 - a = 0
//      x1 = x0 - x^2 - a / 2x
        if(x == 0) return 0;
        
        double a = x, a2 = x;
        do
        {
            a = a2;
            a2 = a - (a * a - x) / (2 * a);
        } while(abs(a - a2) > 0.00001);
        
        return (int)floor(a2);
    }
};

###### tags: `LeetCode` `C++`