Skip to content
Tutorials Center
My learning

Topics

Lesson 4 of 37 ยท Getting Started

Your First Method: Square Roots

Build your first numerical algorithm: the Babylonian square root method, see why it converges so fast, compare it with bisection, and learn how to test it.

How does a calculator find sqrt(2)? It cannot look the answer up, and no finite formula with + - * / gives it. Instead it runs a short iteration. The oldest version of that iteration is more than 3,000 years old and is still the template for Newton's method, the most important root finder in this course.

In this lesson you will build the method from a simple geometric idea, test it properly, and compare it with a slower but safer alternative. Along the way you will practise the workflow every later chapter uses: derive, implement, test against a known value, measure the error.

The idea: average a guess with its partner

Suppose you want sqrt(a) and you have a guess x. If x is too big, then a / x is too small, and the other way round, because their product is exactly a. The true root lies between them. So take the average:

x_new = (x + a / x) / 2

That is the Babylonian (Heron's) method. Picture a rectangle with area a and sides x and a / x. Averaging the sides makes it more square, and a square of area a has side sqrt(a).

flowchart TD
    A["Guess x"] --> B["Partner a / x"]
    B --> C["Average: (x + a/x) / 2"]
    C --> D{"Close to the<br/>previous guess?"}
    D -->|"no"| A
    D -->|"yes"| E["Return x"]

The loop repeats until two successive guesses agree.

Python Babylonian square root

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every case finishes within a few dozen steps, even for 1e10. The starting guess matters little because the method is self-correcting.

Why it is so fast

Look at the error of each step for a = 2. If x has d correct digits, x_new has about 2d. Print the iterates with the true value next to them.

Python Watch the digits double

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The errors fall like 1e-1, 1e-3, 1e-6, 1e-12, then hit machine precision. This is quadratic convergence. You will prove why in the lesson on Newton's method, where this very formula turns out to be Newton's method applied to x^2 - a = 0.

A safer but slower rival: bisection

For comparison, here is a method that needs no clever formula. We know sqrt(a) lies in [0, max(1, a)]. Look at the midpoint: if its square is below a, the root is in the upper half, otherwise in the lower half. Each step halves the interval.

Python Bisection for the square root

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Bisection needs close to fifty steps, Babylonian a few. Bisection gains one binary digit per step (linear); Babylonian doubles the digits (quadratic). The trade-off is typical: the fast method relies on a good formula and a decent start, while the slow one is nearly impossible to break. The bisection lesson develops it fully.

Testing a numerical routine

A short, disciplined test routine catches almost all bugs. Check three kinds of inputs:

Test Examples What it catches
Known answers sqrt(4) = 2, sqrt(2.25) = 1.5 wrong formula
Edge cases 0, very small, very large, 1 division by zero, bad start
Property checks x * x close to a; result matches math.sqrt silent inaccuracy
Python
import math

def check(a):
    root, _ = babylonian_sqrt(a)
    assert math.isclose(root, math.sqrt(a), rel_tol=1e-12), a

for a in (1e-300, 1e-8, 0.5, 2, 144, 1e12, 1e300):
    check(a)

Notice the use of rel_tol (relative tolerance). Comparing a result near 1e150 with an absolute tolerance would be meaningless.

Whenever you write a new method, compare it with the library version on at least ten inputs, including extreme ones, before you trust it.

Beyond square roots

The same idea gives other roots. For the cube root, x_new = (2x + a / x^2) / 3. For the nth root, x_new = ((n - 1) x + a / x^(n-1)) / n. All of these are Newton's method for x^n - a = 0. Reciprocals can even be computed with no division at all: the update x <- x * (2 - a * x) converges to 1 / a using only multiplication and subtraction, a trick used in some hardware.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does averaging x and a/x move closer to sqrt(a)?

    If x is above sqrt(a), then a/x is below it (and vice versa), so their mean is closer to the true root than the worse of the two.
  2. 2. Which convergence does the Babylonian method show near the answer?

    The number of correct digits roughly doubles each step.
  3. 3. Bisection takes about 50 steps for double precision; Babylonian takes a few. What is the benefit of bisection?

    Bisection halves a bracketing interval every time, so it always converges, just slowly.
  4. 4. Why compare your result with math.isclose and a relative tolerance in tests?

    A relative tolerance scales with the size of the answer.

Summary

  • The Babylonian method x <- (x + a/x)/2 converges quadratically to sqrt(a).
  • It is Newton's method for x^2 - a = 0; the same pattern gives cube roots and nth roots.
  • Bisection is slower (one bit per step) but cannot fail when the root is bracketed.
  • Test with known answers, edge cases and comparisons with the library, using relative tolerances.

Next: Absolute and Relative Error