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

сегодня в 15:07

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

Код функции

#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;
}

—

1385

12

Developers, stick with Russians – work in London

Переводы с

карты на карту

Переводы

через QR-Код

Новая функция

«Мой контроль»

Возьми Lumia 925 на тест-драйв сейчас.

Впечатляющие возможности

в стильном тонком корпусе из металла

Boomburum

исследует LTE

Эволюция средств связи

в путешествии по России

Проблемы коммуникации внутри бизнеса?

Смотри бесплатные курсы

и выиграй Xbox

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers.