Methods of computing square roots#Babylonian method

The Heron procedures Heron'sche approximation methods or Babylonian square root is a computational method for calculating an approximation of the square root x of a number a

Method

The iteration equation of Heron process can be derived from the Newton method for the zeros of the quadratic function.

The iteration is:

The starting value of the iteration, as long as it is not equal to zero are arbitrarily set, the iteration always converges. Note that negative values ​​versus the square root of negative converge. A qualified estimate for the start value is obtained from the Taylor series expansion of the binomial series to 1, provide two whose first members of this equation:

Example

The following simple example shows the root of 9 as an approximation of three calculation steps to the true value. With the start value is calculated for the iteration and used in the iteration:

Convergence

It shall apply:

That is, the approximate value comes from the top on the wanted root, and

That is, the method converges to the root.

Since the Heron process can be derived from Newton's approximation method, the convergence order is 2

The method converges very quickly if there is already a good approximation. The number of correct locations is doubled with each step around. However, if the first approximation is bad, it takes many steps to achieve a good approximation.

For example, an integer of 200 binary digits when the root is to be calculated starting with the first approximation, the approximation at every step by about one bit position becomes shorter, i.e., after 100 increments, the approximation, the proper length of 100 points. Then reach six to seven more steps ( ) to correctly calculate all 100 digits before the decimal point.

It is thus appropriate to determine a very precise starting value. In the example, you should use the bit length of identify, and a starting value at half the length first.

Error

For the error of the Heron - sequence applies:

As well as

Geometric illustration of the Heron process

The Heron method is based on the idea that a square area has a side length of. Starting point of the process is any rectangle area. Step by step the aspect ratio of the rectangle is changed so that its shape more and more approximates that of a square, while the surface area remains the same. The side lengths of the rectangle are the approximate values ​​.

In the first step an arbitrary side length of the rectangle is selected. In order for this to have the desired surface area, the second side length of the formula

Calculated. As an example, the root is to be calculated from 9. For a side length of the value 9 is selected, so that calculates the other side length 1. The first rectangle has therefore the following form.

The similarity of this rectangle with a square is low. This is also expressed by the fact that the side lengths 1 and 9 bad approximation for the square root of 9, whose precise value is 3, are.

In order to obtain a better approximation to a square, with the long side must be shortened and the short side can be extended. As a new length of the long side, the mean

Taken the previous two side lengths. The length of the other side is calculated as above

In the example, which is the average side length 5 The corresponding short side has a length of 1.8.

Again, the similarity is to a square still low. However, the new rectangle is compared to the preceding compact.

The procedure is repeated in each further step of Heron process. The mean value of the side lengths of a rectangle corresponding to the length of the long side of the new rectangle, and the length of the short side can be calculated in each case as described above, thereof. In the example to be constructed within the next two steps, the following two rectangles.

The last rectangle is already approximately square. The side length of 3.024 is correspondingly close to 3, the exact value of.

Implemented in software,

The method is particularly suitable for implementation in software, since only basic arithmetic operations are needed, so it is today, given the wide availability of numerical processor hardware but only rarely needed.

If in addition a floating-point representation is used with a two - exponent, the approach is relatively simple, as an example, the square root of 5 is considered and the relative error of the final value (ie abs ( (xi - x) / x) ) follows:

• First, it is cleaved from this two exponent is an even number, so that the exponent is either a -1 or 0 is left, the number is therefore normalized to the interval [ ½, 2]. In this interval, the square root function is only weakly curved curve, ie can be treated numerically well. For example, it is so for the time being only a = 1.25 = treated with the target x 1.118034.
• The starting value for the actual iteration one approximates this curve by an even simpler, which can be calculated directly (without iteration). With this initial calculation of initial value is determined by the following iteration is started. It is this curve more or less start -consuming, with the increasing complex approaches below can possibly save one iteration: a simple constant ( for example 1) Example: x0 = 1; rel. Error = 1.1 * 10-1;
• A line with slope 1/2 and an additive constant of 1 /2 ( as a simplification of the subsequent case ), Example: x0 = 1/2 1.25 / 2 = 1.125; rel. Error = 6.2 * 10-3;
• A line with slope 1/2 and an additive, optimized constant, Example: x0 = 0.929683 / 2 1.25 / 2 = 1.089841; rel. Error = 2.5 * 10-2;
• A straight line with optimized gradient and an additive constant ( considered here in detail ).

Generalization of the method

This method can be generalized so that the nth root is calculated by. The larger, the more steps are needed to calculate the root exactly.

For this, the k-dimensional equivalent of the above geometric derivation is used.

Here, the sequence with an appropriate initial value for the root must be started.

Historical

The procedure was in Mesopotamia already in the time of Hammurabi I (ca. 1750 BC ), a king of Babylon, known .. By 100 AD, it was described by Heron of Alexandria in the first book of his work Metrica.