Глава 5. НЕОСНОВНЫЕ АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ

5.1. ОПЕРАЦИЯ ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ

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

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

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

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

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

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

где есть приближение

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

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

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

с цифрами искомого результата В. Если то в разряде нужно поставить О и переходить к вычислению разряда.

Так как вычисление этого разряда снова начнется с подстановки пробной 1, то в случае можно вместо «стирания» разряде вычесть 1 из разряда.

Аналогичным образом можно вычислять и т. д.

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

0. При этом если то если то

Остаток при можно получить следующим образом}

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

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

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

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

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

Таким образом, сразу получается правильный остаток операция вычисления корня квадратного становится регулярной и подобна операции деления без восстановления остатка. Вычисление корня подобно вычислению частного при делении. При этом роль делителя, постоянного в процессе деления, выполняет «переменный делитель» который сдвигается на один разряд вправо в каждом такте. Так и при делении, вместо сдвига делителя вправо можно сдвигать остаток влево, при этом необходимо предусмотреть два знаковых разряда у остатка из-за возможной потери знака при его сдвиге влево.

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

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

Таким образом, процесс вычисления квадратного корня состоит из ряда однотипных циклов, выполняемых последовательно, и шага округления. В каждом цикле находится очередная цифра корня, аначение которой определяет знак результата алгебраического сложения остатка с «переменным делителем», которому приписывается внак, противоположный знаку предыдущего остатка (в первом цикле остаток — это подкоренное число). Если новый остаток положительный, то в регистр результата операции заносится 1 и формируется новое значение переменного делителя путем приписывания к результату операции справа пары цифр (в первом цикле результат равен 0). Затем остаток сдвигается на один разряд влево и выполняется следующий цикл. Если же новый остаток отрицательный, то в регистр

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

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

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

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

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