Алгоритм деления

Основная сложность при реализации классического метода деления «в столбик» состоит в необходимости угадывать разряды частного на каждой итерации алгоритма. Этот процесс должен быть формализован. Прежде всего заметим, что деление т-разрядного числа  на  п-разрядное (т > п) сводится к последовательности делений (п + 1)-разрядных чисел и на n-разрядное число v,причем , где b – основание системы счисления. Таким образом, необходимо построить алгоритм для нахождения q = , u = (un, un-1, …, u0)b и
v = (vn, vn-1, …, v0)b.
Условие u/v < b может быть переформулировано как и/b < v,т. е.
(un, un-1, …, u1)b < v = (vn, vn-1, …, v0)b.Частное q должно быть единственным целым числом, таким, что .Попытаемся угадать q как
                                   (12)
В данном случае , при этом если q* превышает q,то превышение незначительно. Кроме того, если , то . Это условие носит название условия нормализации. Его можно обеспечить, домножив делимое и делитель на . Дополнительно можно показать, что если , то q* < q,где r* = uпb + un–1 + q*vn–1. В противном случае
q є{q*, q* – 1}.
Исходя из этих соображений, алгоритм вычисления  частного m и остатка n от деления (um+n-1, …, u0)b на (vn-1, …, v0)b имеет вид

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

Автор: Ярмолик, В. Н.