Извлечение квадратного корня

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

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

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

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

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

Рассмотрим сначала метод извлечения квадратного корня с восстановлением остатка.

Для получения цифр корня следует выполнить циклов, каждый из которых распадается на три такта. В первом такте из содержимого сумматора, т.е. из очередного частичного остатка, вычитается делитель, сформированный из уже полученных цифр частного и приписки «01». Очевидно, что в первом цикле делитель представляет собой число «0,01». Во втором такте в случае отрицательного сумматора требуется процедура восстановления остатка путем прибавления к сумматору положительного делителя. В третьем такте формируется очередная (начиная со старшей) цифра корня, равная нулю, если в первом такте сумматор оказался отрицательным, или единице, если в первом такте сумматор оказался положительным. В этом же такте выполняется сдвиг очередного частичного остатка на один разряд влево. По окончании выполнения операции производится округление результата.

Пример.

1. Определение порядка результата.

P_B = P_A/2:

Таким образом, порядок результата P_B = 0,010.

2. Определение мантиссы.

1. -

2. -

3. -

4. -

(окончание примера на следующей странице)

5. -

6. -

Окр.

Окончательно

Извлечение квадратного корня без восстановления остатка является модификацией предыдущего алгоритма. В каждом цикле выполняются два такта. В первом такте в зависимости от знака сумматора выполняется арифметическая операция. Если сумматор положительный, то из него вычитается делитель. Если сумматор отрицательный, то, наоборот, к нему прибавляется положительный делитель. Во втором такте анализируется знак очередного остатка. Если остаток положительный, то очередная цифра частного – единица и приписка к частному для формирования делителя «01». В противном случае очередная цифра частного – нуль и приписка к частному для формирования делителя «11». Одновременно с формированием частного и переменного делителя выполняется удвоение очередного частичного остатка. При этом знаковый разряд может быть искажен, поэтому для сохранения знака следует использовать модифицированный код.

Пример.

Рассмотрим число из предыдущего примера.