Алгоритмы вычисления квадратного корня

Главная Форумы Программирование Алгоритмы и структуры данных Алгоритмы вычисления квадратного корня

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 6 мес., 1 неделя назад.

  • Автор
    Сообщения
  • #3836

    Квадратный корень в программах встречается очень часто, при этом его вычисление достаточно трудоемко. Еще в 1950х годах соответствующая операция была вынесена в специальный математический сопроцессор – центральный процессор отправлял в него запрос и пока выполнялись вычисления он успевал обрабатывать другие важные команды.

    Я не собирал специально литературу по поводу различных алгоритмов вычисления корня, но мне известны два (достаточно очевидных) способа сделать это. Их и рассмотрим.

    Вычисление корня через площадь прямоугольника

    В древней Греции было разработано множество алгоритмов с хорошей геометрической интерпретацией. Не удивлюсь, если и этот алгоритм придумали греки. На самом деле, подумайте откуда берется квадратный корень? – известно, что у квадрата со стороной A площадь равна S = A*A. Из этого простого соотношения следует, что если вам надо вычислить корень из S – нужно построить такой квадрат, что его площадь будет равна S, а длина стороны квадрата как раз и будет искомым корнем (a = sqrt(S)).

    Кстати, аналогичные рассуждения возможны для кубического корня (но при этом площадь квадрата нужно заменить объемом куба). Это прекрасная геометрическая интерпретация, но как же найти длину стороны такого квадрата? – итеративно. Возьмем для начала прямоугольник одна из сторон которого имеет длину S, а другая – 1. Площадь такого прямоугольника совпадает с площадью исходного квадрата, если при этом длины сторон отличаются на величину допустимой погрешности вычислений – то сторона прямоугольника является ответом. Если же стороны различаются слишком сильно – то самый очевидный алгоритм предлагает усреднить одну из сторон (a), а вторую вычислить как b = S/a . За счет того, что одна сторона усредняется, разница длин сторон сокращается. Вторая сторона вычисляется так, чтобы площадь прямоугольника не изменялась.

    Блок-схема такого алгоритма вычисления корня:

    Вычисление корня методом половинного деления

    Метод половинного деления относится к серии алгоритмов, построенных по принципу “разделяй и властвуй”. Он применяется для поиска корней уравнений. Допустим, есть у нас некоторая функция f(x), известно, что функция монотонна на некотором интервале [a,b].

    Монотонность – обязательное требование для использования этого алгоритма, оно означает, что функция либо только возрастает на этом интервале, либо – убывает. В общем, на интервале нет перегибов функции, т.е. точек, в которых производная равна нулю.

    Тогда, если на концах интервала функция имеет разные знаки – она обязательно пересекает горизонтальную ось, т.е. имеет корень. Если f(a) * f(b) > 0 – значит функция на этом интервале корня не имеет.

    Как же найти где именно находится этот корень? – опять же итеративно. Возьмем точку посередине интервала (x = a + (b-a)/2) – по знаку f(x) можно определить где именно находится корень (правее этой точки или левее). Если f(a)*f(x) < 0 – то корень находится на интервале [a,x] при этом заменим b на x и повторим процесс. В противном случае корень находится на [x,b]. Вычисления продолжаются до тех пор, пока интервал поиска корня не сузится достаточно сильно, т.е. пока abs(b-a) > Eps.

    Причем же тут корень квадратный? – заметьте, что для его вычисления достаточно решить уравнение типа x*x = S, т.е. f(x) = x*x - S = 0. Начальное значение интервала поиска – [1,S].

    Блок-схема такого алгоритма вычисления корня:

Для ответа в этой теме необходимо авторизоваться.