[Неочевидные алгоритмы очевидных вещей] Алгоритм 1. Корень квадратный

Серия постов [Неочевидные алгоритмы очевидных вещей] будет содержать алгоритмы действий, которые кажутся очевидными и простыми, но если задать себе вопрос «как это делается?», то ответ является далеко не очевидным. Разумеется, все эти алгоритмы можно найти в литературе. Под катом располагается алгоритм вычисления корня квадратного числа X.

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

Идея

Формируется прямоугольник со сторонами a=1 и b=X. Площадь этого прямоугольника равна S = a * b = X * 1 = X. Преобразовав прямоугольник в квадрат так, что его площадь останется прежней, получим длину стороны, равную корню квадратному из площади фигуры, которая равна Х.
Каждая итерация преобразования прямоугольника в квадрат производится следующим образом:
S = a₀ b₀;
Создаётся новый четырёхугольник, который имеет одну сторону, равную среднему арифметическому сторон текущего прямоугольника, но площадь такую же:
S = a₁ b₁, где a₁ = (a₀+b₀) / 2, а b₁=S / a₁
S = a₂ b₂, где a₂ = (a₁+b₁) / 2, а b₂=S / a₂
…
S = a_n b_n, где a_n = (a_n-1+b_n-1) / 2, а b_n=S / a_n
И так до тех пор пока не |a_n-b_n| < Eps.

Код функции

#define EPS 1e-10
float my_sqrt(float x){
  float S=x, a=1,b=x;
  while(fabs(a-b)<EPS)  a=(a+b)/2; b = S / a;
  return (a+b)/2;
}

Автор: skobeltsyn

Источник