Pull to refresh

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

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


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


Идея


Формируется прямоугольник со сторонами a=1 и b=X. Площадь этого прямоугольника равна S = a * b = X * 1 = X. Преобразовав прямоугольник в квадрат так, что его площадь останется прежней, получим длину стороны, равную корню квадратному из площади фигуры, которая равна Х.
Каждая итерация преобразования прямоугольника в квадрат производится следующим образом:
S = a0 b0;
Создаётся новый четырёхугольник, который имеет одну сторону, равную среднему арифметическому сторон текущего прямоугольника, но площадь такую же:
S = a1 b1, где a1 = (a0+b0) / 2, а b1=S / a1
S = a2 b2, где a2 = (a1+b1) / 2, а b2=S / a2

S = an bn, где an = (an-1+bn-1) / 2, а bn=S / an
И так до тех пор пока не |an-bn| < 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;
}


Tags:
Hubs:
+7
Comments 25
Comments Comments 25

Articles