Операция извлечения квадратного корня

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

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

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

Имеются два пути решения задачи извлечения корня квадратного.

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

B_i+1 = 0,5 (B_i + A/B_i ),

где B_i+1 есть (i+1)-е приближение , i=0, 1, 2,...

Второй способ состоит в создании алгоритма, похожего по структуре на алгоритмы основных арифметических операций, например, деления.

Наиболее простой алгоритм сводится к подбору цифр результата разряд за разрядом, начиная со старшего, т.е. имеющего вес 2^-1.

Вычисление i-й цифры В:

· после получения (i-1)-й цифры В (b_i-1) в i - й разряд В для пробы помещается 1.

· вычисляется разность (A - B_i)²=R_i.

· если R_i > 0, то сохраняется bi=1, иначе b_i = 0.

· перейти к вычислению (i+1)-й цифры.

Определение остатка R_i = A - является сложной процедурой, выполнение которой нежелательно. Поэтому используется рекуррентная формула для получения R_i из R_i-1. Допустим, что найдены первые (i-1) цифр из B=0,b₁b₂b₃...b_i-1. Очевидно, что B_i-1 - наибольшее число из (i-1) разрядов, для которого т.е.

Следующая i-я цифра т.е. B_i=0,b₁b₂...b_i-10 или B_i=0,b₁b₂...1.

При R_i ³ 0 принимается b_i=1, иначе b_i=0.

Остаток R_i при b_i=1 можно получить следующим образом:

Следующая цифра b_i+1 определяется так же, если R_i ³ 0. Если R_i < 0, то прежде чем вычислять следующую цифру, необходимо восстановить предыдущий остаток, т.е. получить

Затем в следующем такте вычислить следующий остаток:

Новая цифра результата равна инверсному значению знаковой цифры остатка R_i+1.

Таким образом, чтобы получить остаток R_i нужно к B_i-1 приписать справа пару цифр 01_, сдвинуть его на (i-1) разрядов вправо и вычесть из предыдущего остатка R_i-1. Если R_i ³ 0, то b_i=1, если R_i < 0, то b_i = 0. В последнем случае необходимо восстановить предыдущий остаток и приступить к вычислению следующей цифры.

Такой способ проще, чем вычисление разности . Он лучше поддается автоматизации и может быть реализован в виде самостоятельной операции.

Как и при делении можно отказаться от восстановления остатка. В этом случае, если R_i < 0, то b_i=0, а в следующем цикле к B_i добавляется не 01, а 11 (дополнительный код) и вычитание заменяется сложением. Для доказательства этого приведем следующие преобразования:

При этом имеется в виду, что B_i-1=0,b₁b₂...b_i-1, a B_i=0,b₁b₂...b_i-10.

Таким образом, если R_i < 0, то в следующем такте вычитание заменяется сложением, в i-й разряд результата записывается 0, и в следующем такте к B_i приписывается справа не 01, а 11.

Таким образом сразу получается правильный остаток R_i-1, операция вычисления корня квадратного становится регулярной и подобной операции деления без восстановления остатка.

Вычисление корня квадратного подобно вычислению частного при делении. Роль делителя, постоянного в процессе деления, выполняет "переменный делитель" B_i, который сдвигается на один разряд вправо в каждом такте.

Как и при делении, вместо сдвига делителя вправо можно сдвигать остаток влево, предусмотрев использование модифицированного кода остатка из-за возможной потери знака при сдвиге влево.

Результат вычисления корня квадратного всегда получается с недостатком, поэтому желательно его округление. Для этого необходимо определить n+1 разряд корня.

Пример. Вычислить значение корня квадратного из числа 0,10111₂,, используя ДСДК и сдвиг текущего остатка без восстановления остатка.

ª Примем значение двоичного числа, из которого надо извлечь корень квадратный, равным 0,10111₂. Для выполнения операции потребуются следующие структурные элементы:

· Сумматор модифицированного кода на 8 разрядов (один дополнительный разряд для образования модифицированного кода, второй - для определения младшего разряда результата.

· Регистр А (РгА) для приема операнда из памяти.

· Регистр В (РгВ) для хранения результатов вычисления значения корня квадратного.

· Регистры D1, D2 (РгD1, РгD2) - вспомогательные регистры для хранения двух бит, приписываемых в конец переменного делителя в соответствии с приведенными выше формулами.

· Регистр С (РгС) для хранения переменного делителя.

· Два счетчика для подсчета числа определенных цифр результата и числа сдвигов вспомогательных регистров.

· Инвертор для реализации сложения (вычитания) переменного делителя с содержимым сумматора.

При выполнении примера полагаем, что в начале выполнения операции текущий остаток равен содержимому РгА. Пример выполнения операции иллюстрируется Табл. 1.

Таблица 1 Пример вычисления значения корня квадратного

В приведенном примере округление не выполнялось. Как видно из таблицы, процесс вычисления корня квадратного состоит из однотипных циклов, в каждом из которых определяется очередная цифра корня. Значение очередной цифры определяет инверсия знака текущего остатка. При положительном остатке в результат заносится 1, а новое значение формируется путем приписывания к первым записанным цифрам результата пары 01. Если текущий остаток отрицателен, то в качестве очередной цифры результата выбирается 0, а для формирования очередного значения переменного делителя к текущему значению корня приписывается пара 11. Затем процедура повторяется.

Для извлечения корня квадратного из числа с плавающей запятой необходимо порядок числа разделить на 2, а из мантиссы извлечь корень по правилам для чисел с фиксированной запятой, приведенным выше. Если порядок нечетный, то необходимо прибавить к порядку 1, затем сдвинуть порядок и мантиссу на один разряд вправо. Так как мантиссы всегда нормализованы и в первом цикле из мантиссы производится вычитание числа 0,01, то первый остаток всегда будет положительным, т.е. первая цифра результата всегда будет 1. Следовательно, при выполнении извлечения корня квадратного никогда не может произойти нарушение нормализации.

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