Несмотря на то что деление принадлежит к редко встречающимся операциям (для универсальных вычислительных машин деление составляет всего 2% от общего числа операций), проблема уменьшения времени деления все-таки актуальна. С одной стороны, даже малое уменьшение времени выполнения деления • может оказаться весьма эффективным для специализированных машин, с другой стороны, общее время, затрачиваемое на выполнение деления, столь велико, что возможно найти пути его существенного сокращения.

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

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

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

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

- щая группа из единиц. Покажем, что эта группа будет состоять из (т- 1)-й единицы. Обозначим через полученный малый отрицательный остаток, а через q нормализованный делитель. Тогда новый остаток может быть выражен как == 2•?o + Ясно, что при ni-l>lRi>0. Следующий остаток R2 имеет вид

. R2 = 2-Ri-q=2-RQ + q.

При /те - 1 > 2 /?2 > О и т. д. Для всех i < т имеем Ri-2f-Ro + д а Ri>0, если m-l>L Отсюда /? i>0," и необходимость записи в частное группы из т-\ единицы доказана,

3. Остаток положителен и близок к q. Вычтем из /?о q. Получим величину Rq==Ro - 7 (в дополнительном или обратном коде), которая является достаточно малой по модулю отрицательной величиной. Пусть в старших разрядах Rq стоит группа из т единиц. Покажем тогда, что в частное можно записать группу из (7Я-1)-й единицы.-/?1 = 2-/?о -9 = 2-/?;+9. При /те - 1 > 1 /?1 > О и т. я- Ri = 2-/?; +q и Ri>0 при т-1> i. Последний остаток R„ = 2-Rl + q. Этот , остаток получается сдвигом R на т единиц влево и прибавлением к результату сдвига делителя.

4. Остаток отрицателен и близок по модулю к q. рбразуем /?о = /?о + В в первых т разрядах стоят нули. Поэтому в частное записывается {т - 1) нуль.

Пример 2.19. Разделить (л:>2==0,1П1110010111 на (д;)2 = 0,1000001000001 по вышеописанному методу формирования групп цифр частного.

Вычисления будем вести в дополнительном модифицированном коде по способу без восстановления остатка. Знак частного 0ф0 = 0.

00.11111100000111 11.0111110111111.

д.,00.0111101010110 - 11.0111110111111

11.1111100010101 -

11.0001010100000

00.1000001000001

11.1001011100001 -00.1000001000001

,00.0001100100010 00.11С0100010000 11.0111110111111

ЮОООП1000001 1111100011000

,00.0100011001111 00.1000110011110 11.0111110111111

,00.0000101011101 00.1010111010000

деление прекращено;

остаток близок к q

передача в частное группы из 4 единиц и сдвиг остатка на 5 разрядов влево остаток близок к q

передача в частное группы из 2 нулей и сдвиг остатка на 3 разряда влево сдвиг остатка на один разряд влево, в частное 1

передача в частное группы из 3 нулей и сдвиг остатка на 4 разряда влево

1,111100011000.

\у/2

Операция извлечения квадратного корня из данного числа не принадлежит к числу арифметических опера-

ций. Однако при работе универсальных вычислительных машин эта операция встречается не так уж редко (около 1% от общего числа операций, выполняемых машиной). В большинстве современных машин извлечение корня представляет собой специальную стандартную подпрограмму, позволяющую с помощью несложного итерационного процесса вычислять значение корня. Примером итерационной формулы, пригодной для вычисления значений корня, может служить формула вида Уй = 0,5(---hyk-i), где на-

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

Для пояснения сущности алгоритма вычисления значения корня предположим, что мы уже определили {т- 1) цифру в выражении корня и ищем /ге-ю цифру. Обозначим подкоренное выражение через jc = 0, jCiJCj... Очевидно, что О, У\У1-Ут-\ есть наибольшее число, квадрат которого не превосходит Пусть

"т-Х--УхУ-Ут-Х?

и . . • .

S„ i = A:.(0,j;i32-3m-il)-Если ii)m-i>0, то очевидно, что у„=1. Если же

ит-! < о» то Угп = о, преобразуем выран<ение для w i следующим образом:

wx = - (О, УгУ2 - Уш-1 + 2-") = = [х-(О, УгУ2 ...Ут-1)\-2-2--0, у,У2-Ут-г--""-= Щп-1 - 2-("-)•0, у,У2 ...Ут-fil.

Итак, для получения значения w необходимо написать справа от О, УгУ-Ут-! комбинацию 01, сдвинуть полученное число на.(/я-1) разряд вправо и