Common table expressions (CTE)

Recursive CTE

D. Iterative calculation of square root

Square root from A number is a solution of equation x * x = A. In the terms of previous point it is a root of equation g(x) = 0, where g(x) = x * x - a. The calculation of this numbers isn`t difficult. In  SQL(Structured Query Language) is a database computer language designed for the retrieval and management of data in relational database management systems (RDBMS), database schema creation and modification, and database object access control management.SQL we may use SQRT(a) or POWER(a, 0.5) for it. Let`s exemplify the method, nevertheless, which is useful in the case when there is no standard function but the contracting mapping is known.

The iterative analytical algorithm for calculation of square root is well known from basic course of mathematics and you can see it here.

It may be written in the form of contracting mapping x = f(x), where

f(x)=1/2*(x+a/x).

 It`s easy to get evidence in that the equation x = 1/2 * (x+a/x) is equivalent to equation x*x = a for x <> 0. The reader with mathematical education may try to prove that this transformation is really contracting, and therefore may be used for iteration process of finding equation`s root.

For illustration of this algorithm let`s note an example of SQL-code for calculation the square root from a = 3:

Console

Execute

WITH Square3(a,b,c) AS
(
 SELECT 1, CAST(3 AS float(53)), CAST(3 AS float(53))
 UNION ALL
 SELECT a+1, 1./2.*(b+3/b), 1./6.*3*(c+3./c) FROM Square3 WHERE a < 7
)
SELECT iteration=a, Exact=sqrt(CAST(3 AS float(53))), Res1=b, Res2=c
FROM Square3;

with Square3(a,b,c) as (  select 1, cast(3 as float(53)), cast(3 as float(53))  UNION all  select a+1, 1./2.*(b+3/b), 1./6.*3*(c+3./c) from Square3 where a < 7 ) select iteration=a, Exact=sqrt(cast(3 as float(53))), Res1=b, Res2=c from Square3;

    Scheme

No scheme

Here the [a] column is introduced for iteration`s number, the [b] and [c] columns calculate square root by two arithmetically equivalent methods. Iterations do not use built-in operations such as SQRT or POWER, but for control we outputted the value of square root which is calculated by using standard function in the [exact] column.

It is evident that the 6th iteration calculations in the third column [Res1] had leaded to coincidence with value of built-in function SQRT(3) in [Exact] column in the FLOAT(53) precision limits. Calculations in the fourth column [Res2] had not. What`s the difference? It is not so obvious, but the reason in that the expression (1./6.) calculates with big mistake as operands are not casted to the 8-byte representation for real numbers (double precision). It affects on all calculations and we have only 5-6 valid significant digits in the result that is corresponds to the theory of calculations with single precision arithmetic.