Серия постов [Неочевидные алгоритмы очевидных вещей] будет содержать алгоритмы действий, которые кажутся очевидными и простыми, но если задать себе вопрос «как это делается?», то ответ является далеко не очевидным. Разумеется, все эти алгоритмы можно найти в литературе. Под катом располагается алгоритм вычисления корня квадратного числа 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;
}
Автор: skobeltsyn
