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 < |f(guess)|)  // delta small      guess = improve(guess);   return guess;

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 <= a and 0 <= n.

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 <= |f(guess)| <= delta?   private boolean goodEnough(double guess) {      return (Math.abs(f(guess)) <= delta);   }   // Newton's Method   private double improve(double guess) {      return guess - f(guess)/df(guess);   }}// a primitive GUIpublic class Main extends Frame {   private TextField root;   private TextField base;   private TextField result;   public Main() {      setTitle("Root Tester");      setLayout(new FlowLayout());      root = new TextField("root", 15);      base = new TextField("base", 15);      result = new TextField("result", 15);      add(root);      add(base);      add(result);   }   public boolean action(Event e, Object o) {      if (e.target == base) {         double d = Double.valueOf(base.getText()).doubleValue();         int i = Integer.valueOf(root.getText()).intValue();         if (0 <= i && 0 <= d) {            Solver s = new Solver(i, d); // make a solver for x^i - d            result.setText("+/- " + String.valueOf(s.solve()));         }         else result.setText("0"); // for now      }      repaint();      return true;   }   public static void main(String args[]) {      Frame m = new Main();      m.resize(300, 200);      m.show();   }}