Как вычисляется квадратный корень

Функция квадратного корня Sqrt(x) в любом языке программирования вычисляется встроенным высокоэффективным алгоритмом как предел следующей последовательности:

Составим алгоритм на PascalABC.NET, используя множественное присваивание.

В переменной b запоминается предыдущее значение переменной a. Вычисления проводятся пока разница между a и b не станет меньше некоторого маленького значения. Чтобы первая итерация обязательно выполнилась, мы инициализируем b очень большим значением:

##
var x := 2.0;
var (b,a) := (real.MaxValue,x);
while Abs(a - b) >= 1e-15 do
  (b,a) := (a,(a + x/a) / 2);
Println(a);
Println(Sqrt(x));

Результат вычисления квадратного корня из 2:

1.41421356237309 
1.4142135623731 

Нетрудно видеть, что результат отличается от стандартной функции Sqrt(x) в 15-й значащей цифре.

Оказывается, для достижения точности 1e-15 требуется всего 6 итераций! На каждой итерации выполняются две операции деления и одна операция сложения. Поэтому суммарно для вычисления Sqrt(2) требуется 12 операций деления и 6 операций сложения.