Find square root of a number in Python without using sqrt or without using any built-in functions

by

Finding the square root of a number is a common task in programming, and there are various ways to do it in Python. One way is to use the sqrt() function from the math module, which is a built-in function that computes the square root of a number. However, there may be situations where you want to find the square root of a number manually in Python.

In this article, we will discuss how to find the square root of a number in Python without using the sqrt() function or without using any other built-in functions. We will explore different methods and compare their complexity to help you choose the best approach for your needs. Here, we will discuss two methods: the bisection method and the Newton-Raphson method, and compare their complexity.

Bisection method

The bisection method is a simple and efficient algorithm for finding the root of a function in a given interval. It works by dividing the interval in half at each iteration and checking which half contains the root. The bisection method has a linear convergence rate, meaning that the error is halved at each iteration.

To compute the square root of a number using the bisection method, you can use the following pseudocode:

def square_root(x):
    # Set the initial interval for the root
    low = 0
    high = x
    # Set the error tolerance
    tolerance = 1e-6
    # Iterate until the interval is small enough
    while high - low > tolerance:
        # Compute the midpoint of the interval
        mid = (low + high) / 2
        # Check if the midpoint is the root
        if mid * mid > x:
            # If not, update the interval
            high = mid
        else:
            # If yes, update the interval
            low = mid
    # Return the midpoint of the final interval
    return mid

print(square_root(4))  # Output: 2.0
print(square_root(9))  # Output: 3.0
print(square_root(16))  # Output: 4.0

In the above bisection method to find the square root in python, we define the square_root() function that takes a number x as an argument and returns its square root. The function initializes the interval for the root and the error tolerance. Then, it enters a loop that iterates until the interval is small enough. Inside the loop, the function computes the midpoint of the interval and checks if it is the root. If it is not, the function updates the interval accordingly. If it is, the function also updates the interval. Finally, the function returns the midpoint of the final interval.

To test the function, we call it with different values of x and print the results to the console. Keep in mind that the bisection method only works for continuous functions and requires an initial interval that brackets the root. To compute the square root of a number, you can use the interval [0, x] as the initial interval.

complexity of the bisection method

The complexity of the bisection method is O(log n), where n is the number of iterations required to reach the desired accuracy. The number of iterations is proportional to the logarithm of the error tolerance, so the bisection method is highly efficient for finding the square root of a number with a high accuracy.

Newton-Raphson method

The Newton-Raphson method is a root-finding algorithm that uses an iterative process to converge on the root of a function. It works by using the derivative of the function to compute a new approximation of the root at each iteration. The Newton-Raphson method has a quadratic convergence rate, meaning that the error is squared at each iteration.

To compute the square root of a number using the Newton-Raphson method, you can use the following formula:

x(i+1) = x(i) - f(x(i)) / f'(x(i))

Where x(i) is the current approximation of the root, f(x(i)) is the value of the function at x(i), and f'(x(i)) is the derivative of the function at x(i).

Here’s an example of how to use the Newton-Raphson method to compute the square root of a number in Python:

def square_root(x):
    # Set the initial approximation of the root
    x0 = x
    # Set the error tolerance
    tolerance = 1e-6
    # Iterate until the approximation is good enough
    while True:
        # Compute the next approximation of the root
        x1 = 0.5 * (x0 + x / x0)
        # Check if the approximation is good enough
        if abs(x1 - x0) < tolerance:
            # If yes, return the approximation
            return x1
        # If not, update the approximation
        x0 = x1

print(square_root(4))  # Output: 2.0
print(square_root(9))  # Output: 3.0
print(square_root(16))  # Output: 4.0

In this example, we define the square_root() function that takes a number x as an argument and returns its square root. The function initializes the approximation of the root and the error tolerance. Then, it enters an infinite loop that iterates until the approximation is good enough. Inside the loop, the function uses the Newton-Raphson formula to compute the next approximation of the root and checks if it is good enough. If it is, the function returns the approximation. If it is not, the function updates the approximation and continues the loop.

To test the function, we call it with different values of x and print the results to the console.

Keep in mind that the Newton-Raphson method requires an initial approximation of the root and may not converge if the initial approximation is not close enough to the root. To compute the square root of a number, you can use the number itself as the initial approximation.

complexity of the Newton-Raphson method

The complexity of the Newton-Raphson method is O(n), where n is the number of iterations required to reach the desired accuracy. The number of iterations is proportional to the inverse of the error tolerance, so the Newton-Raphson method is highly efficient for finding the square root of a number with a low accuracy.

Comparison

In terms of complexity, the bisection method is more efficient than the Newton-Raphson method for finding the square root of a number with a high accuracy. However, the Newton-Raphson method is more efficient than the bisection method for finding the square root of a number with a low accuracy.

Overall, the choice of method depends on the desired accuracy and the initial approximation of the root. The bisection method is a reliable and efficient method for finding the square root of a number, but it requires an initial interval that brackets the root. The Newton-Raphson method is a fast method for finding the square root of a number, but it may not converge if the initial approximation is not close enough to the root.

Leave a Comment