* Question*:

How do you calculate

`sqrt()`

?__ Answer__:

Of course the best way to compute square roots is to use

`Math.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:

How do we improve a bad guess?Newton’s idea is this:guess = 1; while (delta

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 0Dropping 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