Implementing Square Root Calculation with the Newton-Raphson Method

Implementing square root without using in built methods

Calculating the square root of a number is a common operation in programming and mathematics. While most languages provide built-in methods for this, such as Math.sqrt in Java, it’s valuable to understand how these calculations can be performed manually. In this post, we’ll explore how to implement the square root calculation using the Newton-Raphson method—a classic numerical approach.

What is the Newton-Raphson Method?

The Newton-Raphson method is an iterative numerical technique used to find approximations to the roots (or zeroes) of a real-valued function. For square root calculation, we are interested in finding the root of the function f(x) = x^2 - N , where N is the number for which we want to find the square root.

The Algorithm

The method starts with an initial guess and iteratively improves this guess using the formula:

x_{n+1} = 0.5 * (x_n + (N / x_n))

Here’s a step-by-step breakdown:

1. Initialize: Start with an initial guess, x_0 . A reasonable guess is the number itself.

2. Iterate: Use the Newton-Raphson formula to update the guess until the result stabilizes within a specified tolerance level.

3. Stop Condition: The iteration stops when the difference between successive guesses is smaller than a predefined tolerance, \epsilon .

Implementation in Java

Here’s a Java implementation of the Newton-Raphson method for calculating the square root:

public class SquareRootCalculator {
    public static double sqrt(double num) {
        if (num < 0) {
            throw new IllegalArgumentException("Cannot compute the square root of a negative number.");
        }
        
        double epsilon = 1e-10; // Tolerance level for approximation
        double guess = num;
        double sqrtGuess = (guess + num / guess) / 2.0;
        
        while (Math.abs(guess - sqrtGuess) > epsilon) {
            guess = sqrtGuess;
            sqrtGuess = (guess + num / guess) / 2.0;
        }
        
        return sqrtGuess;
    }
    
    public static void main(String[] args) {
        double num = 84630800;
        System.out.println("Square root: " + sqrt(num));
    }
}

Explanation

• Tolerance (epsilon): The value 1e-10 (or 0.0000000001) sets the precision of our result. The loop continues until the change between successive guesses is smaller than this tolerance.

• Iteration Formula: The update formula calculates a new guess based on the average of the current guess and the quotient of N divided by the current guess.

• Stopping Condition: The loop stops when the absolute difference between successive guesses is less than the tolerance.

Why Use Newton-Raphson?

• Efficiency: The Newton-Raphson method converges quickly to the correct value, especially with a good initial guess.

• Understanding: Implementing this algorithm manually helps in understanding numerical methods and their applications in real-world problems.

By mastering such algorithms, you can gain deeper insights into how numerical calculations are performed and how to optimize or troubleshoot them.

Feel free to reach out with any questions or share your implementations and results!