Разработка алгоритма деления

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

. (1.1)

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

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

Блок-схема алгоритма деления чисел без восстановления остатка представлена на рис. 1.2. Алгоритм предусматривает формирование знака результата в соответствии с формулой (1.1) и временное сохранение его в переменной (блоки 2 – 4). После этого знаки операндов обнуляются (блок 5) и выполняется деление модулей чисел и .

На первом этапе выполняется пробное вычитание делителя из делимого (блок 5). Поскольку знаки операндов положительные, появление единицы в знаковом бите разности означает, что и можно продолжать деление. Если же , то деление невозможно. Поэтому формируется признак переполнения (блок 8) и выполнение алгоритма завершается (блок 16).

В процессе определения цифр частного роль очередного остатка играет переменная . Независимо от знака остатка она копируется в переменную , которая затем увеличивается в два раза путем сдвига влево на один разряд (блок 9). В зависимости от знака остатка формируется очередная цифра частного и принимается решение о действии на следующем шаге – вычесть делитель из сдвинутого остатка или прибавить к нему (блоки 10 – 12). После вычитания или сложения проводится сдвиг частного влево на один разряд (блок 13). Тем самым освобождается последний разряд числа для очередной цифры частного. Затем изменяется счетчик цифр частного (блок 13) и проверяется условие выхода из цикла – получение шестнадцати цифр частного, включая и самую первую цифру – «0 целых» (блок 14).

На последнем этапе вычисленное значение частного копируется из переменной в переменную , а знак частного копируется из переменной в знаковый бит переменной (блок 15). На этом алгоритм деления числа на число завершается (блок 16).