loading..
Русский    English
01:45
листать

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

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).
 Легко убедиться в том, что уравнение x = 1/2*(x + a/x) эквивалентно  уравнению x*x = a для x <> 0. Читатель с математическим образованием может попытаться доказать, что это преобразование действительно сжимающее, и, следовательно, может быть использовано для итерационного процесса нахождения корня уравнения.
Для иллюстрации алгоритма приведем пример sql-кода для вычисления квадратного корня из числа a = 3:
Консоль
Выполнить
  1. WITH Square3(a,b,c) AS
  2. (
  3.  SELECT 1, CAST(3 AS float(53)), CAST(3 AS float(53))
  4.  UNION ALL
  5.  SELECT a+1, 1./2.*(b+3/b), 1./6.*3*(c+3./c) FROM Square3 WHERE a < 7
  6. )
  7. SELECT iteration=a, Exact=sqrt(CAST(3 AS float(53))), Res1=b, Res2=c
  8. FROM Square3;

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

iteration    Exact    Res1    Res2
1    1.7320508075688772    3.0    3.0
2    1.7320508075688772    2.0    1.999992
3    1.7320508075688772    1.75   1.7499920000160001
4    1.7320508075688772    1.7321428571428572    1.7321358469571777
5    1.7320508075688772    1.7320508100147274    1.7320438814531474
6    1.7320508075688772    1.7320508075688772    1.7320438793794952
7    1.7320508075688772    1.7320508075688772    1.7320438793795034

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

Bookmark and Share
Страницы: 1 2 3
Тэги:
ALL AND AUTO_INCREMENT AVG battles CASE CAST CHAR CHARINDEX CHECK classes COALESCE CONSTRAINT Convert COUNT CROSS APPLY CTE DATEADD DATEDIFF DATENAME DATEPART DATETIME DDL DEFAULT DELETE DISTINCT DML EXCEPT EXISTS EXTRACT FOREIGN KEY FROM FULL JOIN GROUP BY Guadalcanal HAVING IDENTITY IN INFORMATION_SCHEMA INNER JOIN insert INTERSECT IS NOT NULL IS NULL ISNULL laptop LEFT LEFT OUTER JOIN LEN maker Больше тэгов
Учебник обновлялся
месяц назад
https://exchangesumo.com/obmen/BTC-PSBRUB-sort
©SQL-EX,2008 [Развитие] [Связь] [О проекте] [Ссылки] [Team]
Перепечатка материалов сайта возможна только с разрешения автора.