Square Root Bisection Method170 views

AlgoPill 
 function squareRootBisection(num){
    var min=1, max=num, 
        epsilon = num/1000000, // 10^(-6);
        mid,error;
    // square root of numbers smaller than 1 is bigger than the number
    if(num<=1.0){
        min = num;
        max = 1.0;
    } 
    mid = (min+max)/2;
    error = mid*mid-num;
    while(Math.abs(error)>epsilon){
        if(error<0){
            min = mid;
        } else {
            max = mid;
        }
        mid = (min+max)/2;
        error = mid*mid-num;
    }
    return mid;
}

Problem statement: given a number, find its square root.

Solution: Use Bisection method. Square root of a positive number greater than 1 lies between 1 and the number itself. The approximate value of square root can be found by doing a binary search in this range. We take mid of the range as initial guess. if guess² < number , it means that square root must lie in (mid, number) range else is lies in (1, mid) range. Thus this one step reduces the range by a factor of two. We keep on narrowing down on the square root in every iteration until the error (guess² – number) is within some epsilon bound.

Post a Comment

You must be logged in to post a comment.