sqrt_double.cpp File Reference

Calculate the square root of any positive real number in \(O(\log N)\) time, with precision fixed using bisection method of root-finding. More...

#include <cassert>
#include <iostream>

Include dependency graph for sqrt_double.cpp:

Functions
double	Sqrt (double a)
int	main ()

Detailed Description

Calculate the square root of any positive real number in \(O(\log N)\) time, with precision fixed using bisection method of root-finding.

See also

Can be implemented using faster and better algorithms like newton_raphson_method.cpp and false_position.cpp

Function Documentation

main()

int main

(

void

)

main function

           {
    double n{};
    std::cin >> n;
    assert(n >= 0);
    // Change this line for a better precision
    std::cout.precision(12);
    std::cout << std::fixed << Sqrt(n);
}

Here is the call graph for this function:

Sqrt()

double Sqrt

(

double

a

)

Bisection method implemented for the function \(x^2-a=0\) whose roots are \(\pm\sqrt{a}\) and only the positive root is returned.

                      {
    if (a > 0 && a < 1) {
        return 1 / Sqrt(1 / a);
    }
    double l = 0, r = a;
    /* Epsilon is the precision.
    A great precision is
    between 1e-7 and 1e-12.
    double epsilon = 1e-12;
    */
    double epsilon = 1e-12;
    while (l <= r) {
        double mid = (l + r) / 2;
        if (mid * mid > a) {
            r = mid;
        } else {
            if (a - mid * mid < epsilon) {
                return mid;
            }
            l = mid;
        }
    }
    return -1;
}

Here is the call graph for this function: