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

в 11:07, , рубрики: Алгоритмы, математика, численные методы, метки:

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

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js