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

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

При вычислении квадратного корня (для чисел с фиксированной запятой) подкоренное выражение должно быть положительным и меньше единицы.

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

В сумматор заносится подкоренное выражение. Далее необходимо выполнить (n-2) цикла, каждый из которых может содержать три такта:

1) из значения на сумматоре вычитается содержимое переменного делителя (РгД) и определяется очередная цифра результата, которая равна инверсии знака сумматора;

2) если после выполнения вычитания содержимое сумматора меньше нуля, то нужно выполнить восстановление содержимого сумматора путем сложения его с переменным делителем;

3) производится сдвиг содержимого сумматора на один разряд влево и формируется новый переменный делитель.

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

Схема алгоритма извлечения квадратного корня в соответствии с описанным алгоритмом изображена на рис. 4.7.

Р ис. 4.6. Схема алгоритма ускоренного деления с анализом двух разрядов делителя

Рис. 4.6. Схема алгоритма ускоренного деления с анализом двух разрядов делителя (окончание)

Рис. 4.7. Схема алгоритма вычисления квадратного корня

Буквами y_i обозначены разряды регистра результата (РгР). Начальное значение счетчика во всех алгоритмах принимается равным (n-2), где n – число разрядов исходных чисел, так как используются модифицированные коды.

Рассмотрим пример для операции вычисления квадратного корня для числа с фиксированной запятой. Извлечем квадратный корень из числа А = 0,101111 по разработанному алгоритму.

См = 0,101111 РгР = 0 (регистр результата)

⁺1,110000 РгД = 0,01 (переменный делитель)

I 1) См=См-РгД= 0,011111 РгР = 0,1 (так как См>0)

3) См = См← = 0,111110 РгД = 0,101

⁺1,011000

II 1) См=См-РгД= 0,010110 РгР = 0,11 (См>0)

3) См = См← = 0,101100 РгД = 0,1101

⁺1,001100

III 1) См=См-РгД= 1,111000 РгР = 0,110 (так как См<0)

⁺ 0,110100

2) См=См+РгД=0,101100

3) См = См← = 1,011000 РгД = 0,11001

⁺1,001110

IV 1) См=См-РгД= 0,100110 РгР = 0,1101 (так как См>0)

3) См = См← = 1,001100 РгД = 0,110101

⁺1,001011

V 1) См=См-РгД= 0,010111 РгР = 0,11011 (так как См>0)

3) См = См← = 0,101110 РгД = 0,1101101

⁺1,0010011

VI 1) См=См-РгД= 0,010111 РгР = 0,110110 (так как См<0)

В циклах I, II, IV и V пропущен второй такт, потому что сумматор положителен и восстановление остатка не требуется.

Ответ: В = = 0,110110.

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

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

Библиографический список

1. Потапов В.И., Потапова Л.О. Введение в информатику и вычислительную технику: Учеб. пособие. – Омск: Изд-во ОмГТУ, 1995. – 138 с.

2. Савельев А.Я. Основы информатики: Учебник. – М.: Изд-во МГТУ, 2001. – 327 с.

3. Операции двоичной и десятичной арифметики в ЭВМ: Метод. указания к практическим занятиям по курсу «Прикладная теория цифровых автоматов» / Сост. И.А. Пальянов. – Омск: Изд. ОмПИ, 1990. – 36 с.

4. Потапов В.И. Методы ускоренного выполнения арифметических операций в ЦВМ: Учеб. пособие. – Омск: Изд. ОмПИ, 1980. – 87 с.

5. Савельев А.Я. Арифметические и логические основы цифровых автоматов: Учебник. – М.: Высш. школа, 1980. – 255 с.

6. Каган Б.М. Электронные вычислительные машины и системы: Учеб. пособие для вузов. – М.: Энергоатомиздат, 1991. – 592 с.

7. Гаврилов Ю.В., Пучко А.Н. Арифметические устройства быстродействующих ЭЦВМ. – М.: Сов.радио, 1970. – 279 с.

8. Карцев М.А. Арифметика цифровых машин. – М.: Наука, 1969. – 575 с.

9. Моделирование на ЭВМ алгоритмов выполнения арифметических опера­ций и синтез управляющих автоматов: Метод. указания / Сост. И.А. Пальянов, О.П. Шафеева. – Омск: Изд. ОмПИ, 1988. – 36 с.

10. Папернов А.А. Логические основы цифровой вычислительной техники. – М: Сов. радио, 1972. – 592 с.

Виктор Ильич Потапов,

Ольга Павловна Шафеева

Учебное издание