Метод бисекции в двоичной системе счисления на примере вычисления квадратного корня

Метод бисекции или метод деления отрезка пополам — простейший численный метод для вычисления корней уравнения вида f(x)=0 на интервале [a;b], учитывая то, что функция на данном отрезке непрерывна и меняет знак. Графически это показано на рисунке 1.

Рис. 1. Графическое изображение метода бисекции

Общая схема работы алгоритма следующая:

1.      Выбираем такие a и b, что f(a) и f(b) имеют разные знаки.

2.      Вычисляем c=(a+b)/2.

3.      Сравниваем знаки функций f(a), f(b), f(с).

4.      Производим перенос одной из точек a или b в точку с, в которой знак функции f(c) совпадает со знаком f(a) или f(b).

5.      Проверяем условие модуль(f(c))<e, где e — требуемая точность.

6.      Если требуемая точность не достигнута, то возвращаемся к пункту 2.

Данный метод дает следующее приближение к корню: , где n — количество итераций. Метод имеет сходимость по закону геометрической прогрессии с коэффициентом 1/2. Данный алгоритм можно реализовать на языке программирования или создать модель в математическом пакете, табличном процессоре.

Интересно выглядит работа алгоритма в двоичной системе счисления. Чтобы приблизиться к теме вычисления значения квадратного корня в двоичной системе счисления, проанализируем работу алгоритма в десятичной системе.

Для вычисления квадратного корня  требуется решить уравнение вида . Для поиска корня воспользуемся исследуемым методом. Корень лежит в интервале . В таблице 1 представлены результаты расчета. В таблице показаны первые 40 шагов итерации для исследования точности вычислений. К 40-му шагу итерации достигается точность 10 десятичный знаков.

Таблица 1

Результаты вычисления

Построим график отклонения значения вычисленного корня от точного значения и построим линию тренда.

Рис. 2. Зависимость погрешности вычислений от количества итераций

Хорошо видно, что для достижения точность вычислений в 2–3 десятичных знака требуется около 16–18 итераций.

Перейдем к изучению вычисления значения квадратного корня в двоичной системе счисления. Немного истории. С появлением электронных вычислительных машин после возможности выполнения 4 арифметических операций появилась возможность вычисления квадратного корня. В первую очередь это было связано с тем, что вычисление корня в двоичной системе счисления довольно простое, и, что самое главное, была возможность аппаратной реализации вычисления. Поэтому на механической машине Готфрида Лейбница, работающей в двоичной системе счисления, была возможность вычисления квадратных корней. Да и первые калькуляторы могли выполнять 4 арифметических действия и вычислять квадратный корень. Все это было реализовано аппаратно. Это не единственный метод аппаратного вычисления корня [1, с. 3]. Но это классический алгоритм для понимания процесса вычислений. С развитием техники, увеличением скорости вычислений, появилась возможность делать это программно. Однако, методы не устаревают, а обретают новую форму. Перенесем алгоритм вычисления в двоичную систему счисления. Для понятности изложения примем, что число представлено с фиксированной запятой, имеющей по 8 бит для целой и дробной частей. Число 150 представим как 10010110.00000000₂. Так же, как и в выше описанном случае, выбираем интервал поиска корня. В данном случае на интервале . В двоичной системе счисления это будет .

Таблица 2

Результаты вычисления  в двоичной системе счисления

Точное значение корня . Полученное значение с помощью бисекции .

Аппаратно деление на 2 в двоичном коде осуществляется просто — сдвигом регистра, хранящего число, на 1 разряд вправо. Метод бисекции хорошо подходит для использования его в двоичной системе счисления. Метод содержит такие операции, как сложение, умножение, деление на 2 и возведение числа в квадрат. Все функции реализуются на аппаратном уровне. Следует заметить, что точность вычислений ограничена только разрядной сеткой вычислительной машины.

Погрешность составила 0,005, т. е. мы получили достоверность не более 2-х десятичных знаков. Связано это в первую очередь с 8-битным представлением десятичной части числа. Вес младшего разряда составляет 2–⁸=0,00390625. Значит, получить заданную точность можно только увеличив разрядную сетку.

Зависимость точности расчетов от разрядности машины при аппаратном решении задачи представлена в таблице 3.

Таблица 3

Зависимость точности расчетов от разрядности машины

Ближе к практике лежит устройство поразрядного взвешивания. Алгоритм работы такого устройства следующий:

1.      В старшем разряде r_n устанавливается «1».

2.      Число возводится в квадрат. Сверяется с введенным числом x.

3.      Если число меньше, то в регистре оставляют «1», если больше — записывают «0».

4.      Переходят к следующему разряду r_i. Повторяют действия пунктов 2–4 до тех пор, пока не будет проверен последний разряд r₀.

В результате результат достигается за n итераций, где n — количество разрядов.

В нашем случае понадобится 16 итераций для вычисления квадратного корня — итераций будет столько, сколько разрядов имеет разрядная сетка. Одно из таких устройств описано в [2, с.224]. Задачи вычислений, часто, критичны ко времени выполнения. Например, обработка сигналов в реальном времени. Для этого разрабатываются различные специализированные ИС (интегральные схемы). АЦП, ЦАП, имеющие в своей структуре устройства взвешивания. ИС, реализующие БПФ для обработки анализируемых сигналов. ПЛИС, позволяющие задать желаемую структуру цифрового устройства в виде принципиальной электрической схемы.

Рис. 3. Схема выбора реализации вычислений

Перед разработкой системы следует четко определиться с реализацией аппаратно-программного комплекса, решить, какие задачи будут решены с помощью аппаратной части, что — с помощью языков программирования.

Литература:

1.      Патент RU 2005316 Российская Федерация, МПК G06F007/552. Устройство для возведения в квадрат и извлечения квадратного корня/ Олейников В. А.; заявитель и обладатель патента: Самарский государственный технический университет.

2.      Карцев М. А. Арифметика цифровых машин. — Москва: Издательство «Наука», 1969. — 576 с.