LeetCode: Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

---

There are two ways. One is binary search, each time we try half of the current value until to the right one. The other one is Newton Method. It uses a iterative function f(x) = x - (x * x - input)/2x = (x + input/x) /2 where x is used for iteration. We can set up x as our first guess number for the square root. In the source code of Quake III, it sets the first guess number as a constant 0x5f375a86 and the efficiency is amazing.

C++ Code in binary search:

int sqrt(int x){
    if(x <= 0){
        return 0;
    }
    if(x == 1){
        return 1;
    }
    long long start = 0, end = x;
    while(start <= end){
        long long mid = start + (end-start)/2;
        long long tmp = mid * mid;
        if(tmp == x){
            return mid;
        }else if(tmp < x){
            start = mid + 1;
        }else{
            end = mid - 1;
        }
    }
    
    return start * start <= x ? start : start-1;
}

C++ Code in Newton method:

/*
 * func: sqrt
 * goal: compute and return the square root of x
 * @param x: input number x
 * return: square root number
 */
int sqrt(int x){
    //Set the precision
    const float EPS = 0.000000001;
    if(x==0)
        return 0;
    
    float dividend = x;
    float val = 0x5f3759df;
    float last;
    do
    {
        last = val;
        val =(val + dividend/val) / 2;
    }while(abs(val-last) > EPS);
    int result = val;
    if(result * result > x)
        result--;
    return result;
}

Python Code:

# func: implement the sqrt function
# @param x: input number x
# @return: square root of x
def sqrt(x):
    EPS = 0.0000000001
    if x == 0:
        return 0
    trial = float(x)
    val = (trial + x/trial) / 2
    while abs(val-trial) > EPS:
        trial = val
        val = (trial + x/trial) / 2

    result = int(val)
    if result * result > x:
        result -= 1
    return result

Reference Link:

1. 水中的鱼: [LeetCode] Sqrt(x) 解题报告: http://fisherlei.blogspot.com/2013/01/leetcode-sqrtx.html

2. sqrt函数分析 - c语言程序开发技术文章 - 红黑联盟: http://www.2cto.com/kf/201206/137256.html

3. Newton's method - Wikipedia, the free encyclopedia: http://en.wikipedia.org/wiki/Newton's_method#Square_root_of_a_number