devxlogo

How to calculate sqrt()

How to calculate sqrt()

Question:
How do you calculate sqrt()?

Answer:
Of course the best way to compute square roots is to useMath.sqrt(),but I assume your question is academic. I’m not sure of the bestway to find square roots, but historically, Newton’s Method is themost significant.

Newton’s Method tells us how to approximate an x-interceptof a differentiable curve described by the equation y = f(x). Howdoes this help us to find the square root of 42? Well, thex-intercepts of the parabola y = x^2 – 42 occur at sqrt(42) and-sqrt(42).

The x-intercept of a curve y = f(x) occurs at a point x = a such thatf(a) = 0. So, Newton’s Method iterates a sequence of progressivelybetter guesses until f(guess) is acceptably close to 0:

guess = 1;   while (delta  
How do we improve a bad guess?Newton’s idea is this:
Draw a line tangent to the curve at the point (guess, f(guess)).
Using calculus, it’s pretty easy to get the equation for this line:
y – f(guess) = slope * (x – guess)
where slope = f'(guess) = the derivative of f at x = guess.

Newton reasoned that this line crudely approximates the curve y = f(x)near the point of tangency, and therefore the x-intercept of this linecrudely approximates the x-intercept of y = f(x).

It’s easy to calculate the x-intercept of this line. Just set y = 0 andsolve for x:

x = guess – f(guess)/f'(guess)
Hence:
improve(guess) = guess – f(guess)/f'(guess)
>From an implementation standpoint, the only complication is computingf'(x). Again we dust off our calculus book, where we discover
f'(x) = limit (f(x + delta) – f(x))/delta as delta tends to 0
Dropping the limit and choosing delta to be suitably small shouldgive us an acceptable approximation of f'(x).

Here’s a Java implementation with a crude GUI. It can be used tofind the n-th root of any real number a where 0

import java.awt.*;// A system for approximating n-th root of aclass Solver {   private int n;   private double a;   private static double delta = 0.00000001; // controls accuracy   private static double initGuess = 1;   // constructs a solver for x^n – a   public Solver(int x, double y) { n = x; a = y; }   // your basic iterator for the improve method   public double solve() {      double guess = initGuess;      while(!goodEnough(guess))         guess = improve(guess);      return guess;   }   // f(x) = x^n – a = the function we’re solving   private double f(double x) {      return Math.pow(x, n) – a;   }   // df(x) = f'(x), approximately   private double df(double x) {      return (f(x + delta) – f(x))/delta;   }   // 0 

devx-admin

Share the Post: