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:

Go to the source code of this file.

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

Definition in file sqrt_double.cpp.

Function Documentation

main()

int main

(

void

)

main function

Definition at line 42 of file sqrt_double.cpp.

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

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.

Definition at line 16 of file sqrt_double.cpp.

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