Общие табличные выражения (CTE)

Рекурсивные СТЕ

D. Итерационное вычисление квадратного корня

Квадратный корень из числа a – это решение уравнения x*x = a. В терминах предыдущего пункта это корень уравнения g(x) = 0, где функция g(x) = x*x - a. Вычисление этих чисел SQL-запросом труда не представляет - есть встроенная функция sqrt(a) или power(a,0.5). Тем не менее, проиллюстрируем на примере нахождения квадратного корня  подход, который может использоваться в случаях, когда нет соответствующей встроенной функции, а сжимающее отображение известно.

Итерационный аналитический алгоритм для вычисления квадратного корня известен из курса школьной математики, и изложен, например, здесь.

Его можно записать в виде сжимающего отображения x = f(x), где

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

Консоль

Выполнить

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;

    Схема

Нет схемы

Здесь столбец [a] введен для вывода номера итерации, столбцы [b] и [c] вычисляют квадратный корень двумя арифметически эквивалентными способами. Итерации не используют встроенные операции sqrt или power, но для контроля мы вывели в колонке exact значение квадратного корня, вычисленное с помощью встроенной функции.

Видно, что уже на 6-й итерации вычисления в третьем столбце [Res1] привели к совпадению со  значением встроенной функции [Exact] в пределах точности FLOAT(53) для  квадратного корня из трех. Вычисления в четвертом столбце [Res2]  – нет. В чем же причина таких различий? Не сразу очевидно, но причина в том, что выражение (1./6.) вычисляется с большой ошибкой, так как операнды не приведены к 8-байтовому представлению вещественных чисел (двойная точность). Это повлияло на все вычисления, и мы получили только 5-6 правильных значащих цифр в результате, что согласуется с теорией вычислений в вещественной арифметике с одинарной точностью.