О генерации числовых последовательностей в SQL Server

В очередной реализации MS SQL Server 2005 появилась возможность использования рекурсивных CTE   конструкций, позволяющих реализовывать циклы для генерации числовых последовательностей и итерационных вычислений.

Введение в рекурсии MS SQL Server можно найти в соответствующих руководствах Microsoft, учебнике  и Интернете. В данном параграфе мы рассмотрим только новые примеры, помогающие в ее практическом освоении.  Самым простым примером использования рекурсивного CTE является генерация ограниченной числовой последовательности натурального ряда: 1,2,3, … N.

WITH Series(a) AS  
(  
 SELECT 1  
 UNION ALL  
 SELECT a+1 FROM Series WHERE a < 100  
)  
  
SELECT * FROM Series;

Эта конструкция предназначена для генерации последовательности целых чисел (в виде одноколоночной таблицы) от 1 до 100.

А. Итерационные вычисления

В элементарной и высшей математике есть много интересных последовательностей, обладающих замечательными свойствами. Некоторые последовательности сходятся, и их можно использовать для реализации вычислительных алгоритмов или для вычисления алгебраических и трансцендентных чисел, значений тригонометрических функций, для нахождения корней уравнений, решения систем линейных алгебраических уравнений и пр. Другие последовательности, такие как факториал n!, коэффициенты бинома Ньютона, числа Фибоначчи представляют собой расходящиеся последовательности, которые имеют широкое использование в теории вероятности и математической статистике.

Эти последовательности получаются с помощью итераций (рекурсий SQL Server), например:
A1, A2, A3, A4 = fun(A1, A2, A3).

Здесь A1, A2, A3 - начальные значения для итерационного процесса, fun - функция для вычисления 4-го, пятого и т.д. чисел, которая всегда задействует предыдущие 3 числа. Предположим, что процесс стартует с трех одинаковых чисел A1 = A2 = A3 = 1. Тогда схема реализации с использованием рекурсивных CTE будет иметь следующий вид:

with Table(iter, A1, A2, A3, A4) as  
(  
 select iter = 1, A1 = 1, A2 = 1, A3 = 1, A4 = fun(1, 1, 1)  
 union all  
 select iter + 1, A1 = A2, A2 = A3, A3 = A4, A4=fun(A2, A3, A4)  
 from Table where iter < 50  
)  
  
select * from Table;

Здесь колонка iter введена для вывода номера итерации, колонка [A1] содержит пятьдесят первых членов последовательности, [A2], [A3] и [A4] – вспомогательные колонки для хранения необходимых промежуточных результатов.

Обобщением такого подхода является следующий пример. Пусть n >= 1, m >= 1. Тогда последовательные вычисления

A[n+1] = fun(A[1], A[2], …, A[n])

A[n+2] = fun(A[2], A[3], …, A[n+1])

…

A[n+m] = fun(A[m], A[m+1], …, A[m+n-1])

приводят к генерации m (m >= 1) новых членов последовательности A[n+1],…, A[n+m].

Мы не будем приводить примера использования рекурсии в общем случае, так как это возможно разве что в виде некоторого псевдокода. Читатели могут попытаться построить конкретные примеры самостоятельно. Отметим, что результирующая таблица выглядит следующим образом:

A[1]    A[2]    …    A[n]      A[n+1]  
A[2]    A[3]    …    A[n+1]    A[n+2]  
…  
A[m+1]  A[m+2]  …    A[m+n-1]  A[m+n]  

B. О последовательности чисел Фибоначчи

Последовательность Фибоначчи может быть вычислена с помощью следующей итерационной формулы:

A[i+2] = A[i] + A[i+1];  i = 1,…, n; A[1] = A[2] = 1.

Здесь очень легко увидеть аналогию с общим случаем предыдущего пункта, если ввести функцию f(x,y)=x+y.
Для хранения номера итерации i можно использовать колонку [iter], для A[i] используется колонка [a], для A[i+1] и A[i+2] - колонки [b] и [c]. Колонка [d] не потребуется. Используя общий подход, расчет чисел Фибоначчи можно выразить следующим кодом:

with Fibonacci(iter,a,b,c) as  
(  
 select iter=1, a=1, b=1, c=1+1  
 UNION all  
 select iter+1, a=b, b=c, c=b+c  
 from Fibonacci where b < 1000  
)  
select * from Fibonacci;

Приведем результат запроса для вычисления чисел Фибоначчи, меньших 1000 (они
находятся во втором столбце таблицы).

С. Нахождение корней уравнений

Большой раздел математического и функционального анализа посвящен нахождению корней уравнений функции одного и многих переменных. Корнем уравнения g(x) = 0 называется число r (или вектор r), удовлетворяющее условию: g(r) = 0. Общим методом решения таких уравнений является сведение задачи к задаче о неподвижной точке:

x=f(x).

Смысл такого сведения состоит в нахождении такой функции f, при которой уравнения g (x) = 0 и x = f(x) являются эквивалентными. Кроме того, оператор f должен быть сжимающим. То есть, если значение r1 находится рядом с решением r, то значение r2=f(r1) должно быть еще ближе к решению:
abs(r-r2) < A * abs(r-r1), где положительная константа A меньше единицы (A<1) и не зависит от выбора значения r1.

Сжимающих отображений может быть много. Предпочтительными являются те из них, для которых константа A принимает меньшее значение. Чем меньше константа, тем быстрее сходится процесс нахождения корня уравнения g(x):

r2 = f(r1), r3 = f(r2),  r4 = f(r3) …

Приведем иллюстрирующий пример на SQL.

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

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

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

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

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

 Легко убедиться в том, что уравнение x = 1/2*(x + a/x) эквивалентно  уравнению x*x = a для x <> 0. Читатель с математическим образованием может попытаться доказать, что это преобразование действительно сжимающее, и, следовательно, может быть использовано для итерационного процесса нахождения корня уравнения.
Для иллюстрации алгоритма приведем пример sql-кода для вычисления квадратного корня из числа a = 3:

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 правильных значащих цифр в результате, что согласуется с теорией вычислений в вещественной арифметике с одинарной точностью.