Алгоритм деления — алгоритм, вычисляющий для двух данных целых чисел и их частное и/или остаток, результат деления с остатком. Некоторые из алгоритмов предназначены для вычислений вручную, другие реализованы в цифровых схемах и программном обеспечении.
Алгоритмы деления разбиваются на две большие категории: медленные и быстрые. Алгоритмы медленного деления дают по одному знаку результата за итерацию. Примерами медленного деления служат алгоритмы деления с восстановлением, без восстановления и SRT. Методы быстрого деления начинаются с аппроксимации конечного частного и дают вдвое больше знаков в конечном результате на каждой итерации. Алгоритмы Ньютона — Рафсона и Гольдшмидта попадают в эту категорию.
Варианты этих алгоритмов позволяют использовать быстрые алгоритмы умножения. В результате этого для больших целых чисел время вычисления, необходимое для деления, будет тем же самым (с точностью до постоянного множителя), что и время, необходимое для выполнения умножения, какой бы алгоритм из перечисленных ни был применён.
Далее используются обозначения , где — числитель (делимое) — знаменатель (делитель) являются входными числами, а — частное — остаток
являются выходными данными.
Деление путём вычитаний Простейший алгоритм, исторически встроенный в алгоритм поиска наибольшего общего делителя и представленный в Началах Евклида, Книга VII Предложение 1, находит остаток деления двух положительных целых чисел с помощью только вычитания и сравнения:
R := N while R >= D do R := R − D end return R
Доказательство существования и единственности частного и остатка (описано в статье Деление с остатком) даёт полный алгоритм деления, основанный на сложениях, вычитаниях и сравнениях:
function divide(N, D) if D = 0 then error(DivisionByZero) end if D < 0 then (Q, R) := divide(N, −D); return (−Q, R) end if N < 0 then (Q,R) := divide(−N, D) if R = 0 then return (−Q, 0) else return (−Q − 1, D − R) end end -- Здесь N >= 0 и D >= 0 return divide_unsigned(N, D) end
function divide_unsigned(N, D) Q := 0; R := N while R >= D do Q := Q + 1 R := R − D end return (Q, R) end
Эта процедура всегда даёт . Будучи очень простым, алгоритм требует шагов, а потому экспоненциально медленнее, чем алгоритмы наподобие длинного деления. Алгоритм полезен, если известно, что мало, поскольку число шагов зависит от величины частного.
Деление столбиком
Деление столбиком является стандартным алгоритмом деления многозначных чисел в десятичной системе счисления, используемым для вычислений вручную. Алгоритм постепенно продвигается по делимому слева направо, вычитая наибольшее возможное кратное делителя на каждом шаге. Множитель становится цифрой в частном, а конечная разность становится остатком от деления.
Когда алгоритм используется по основанию 2, этот метод образует базис для деления натуральных чисел с остатком. является вариантом деления в столбик, пригодным для деления на одну цифру. Алгоритм , известный также как метод неполных частных, является менее эффективным видом деления столбиком, но более понятным. Возможность вычитать большее количество кратных, чем используемое в данный момент на каждом шаге, даёт больше свободы для создания вариантов деления в столбик.
Деление целых чисел (без знака) с остатком
Приведённый алгоритм, двоичная версия известного деления в столбик, делит на , помещая частное в и остаток в . Все значения трактуются как целые числа без знака.
if D = 0 then error(DivisionByZeroException) end -- Деление на ноль Q := 0 -- Начальные значения частного и остатка полагаем равны 0 R := 0 for i := n − 1 .. 0 do -- Здесь n равно числу бит в N R := R << 1 -- Сдвиг влево числа R на 1 бит R(0) := N(i) -- Полагаем младший бит R равным биту i делимого if R >= D then R := R − D Q(i) := 1 end end
Пример Возьмём () и ()
Шаг 1: Set R = 0 and Q = 0 Шаг 2: Take i = 3 (на единицу меньше числа бит в N) Шаг 3: R = 00 (сдвиг влево на 1) Шаг 4: R = 01 (полагаем R(0) равным N(i)) Шаг 5: R < D, так что пропускаем команду
Шаг 2: Set i = 2 Шаг 3: R = 010 Шаг 4: R = 011 Шаг 5: R < D, пропускаем команду
Шаг 2: Set i = 1 Шаг 3: R = 0110 Шаг 4: R = 0110 Шаг 5: R >= D, команда выполняется Шаг 5b: R = 10 (R−D) Шаг 5c: Q = 10 (полагаем Q(i) равным 1)
Шаг 2: Set i = 0 Шаг 3: R = 100 Шаг 4: R = 100 Шаг 5: R >= D, команда выполняется Шаг 5b: R = 0 (R−D) Шаг 5c: Q = 11 (полагаем Q(i) равным 1)
Конец () и .
Методы медленного деления Все методы медленного деления основываются на стандартном рекуррентном отношении
где: является j-м частичным остатком деления B − основание счисления (равно обычно 2 в компьютерах и калькуляторах) является цифрой частного в позиции , где позиции цифр пронумерованы от менее значащих цифр (0) к более значащим () − число знаков в частном − делитель
Восстанавливающее деление Восстанавливающее деление работает с дробными числами числами с плавающей запятой и зависит от предположения .
Цифры частного формируются из набора .
Основной восстанавливающий алгоритм для двоичного (по основанию 2):
R := N D := D << n -- R и D должны быть словами вдвое длиннее, чем N и Q for i := n − 1 .. 0 do -- Например, 31..0 для 32 бит R := 2 * R − D -- Пробное вычитание из сдвинутого значения (умножение на 2 есть сдвиг в бинарной интерпретации) if R >= 0 then q(i) := 1 -- Результат - бит 1 else q(i) := 0 -- Результат - бит 0 R := R + D -- Новый частичный остаток равен (восстановленному) сдвинутому значению end end
-- Здесь: N = делимое, D = делитель, n = число бит, R = частичный остаток, q(i) = бит № i частного
Вариант алгоритма, не осуществляющий явно , сохраняет его, а потому не нужно добавлять обратно в случае .
Невосстанавливающее деление Невосстанавливающее деление использует набор цифр для цифр частного вместо . Алгоритм более сложен, но имеет преимущество: когда он реализуется в микросхемах, имеется всего одно принятие решения и одно сложение/вычитание на бит частного. Нет шага восстановления после вычитания, что может сократить число операций вдвое, и позволяет выполнить алгоритм быстрее. Алгоритм невосстанавливающего деления для двоичных (по основанию 2) положительных чисел:
R := N D := D << n -- R и D должны быть словами вдвое длиннее, чем N и Q for i = n − 1 .. 0 do -- Например, 31..0 для 32 бит if R >= 0 then q[i] := +1 R := 2 * R − D else q[i] := −1 R := 2 * R + D end if end
-- Здесь: N = делимое, D = делитель, n = число бит, R = частичный остаток, q(i) = бит №i частного.
Если следовать этому алгоритму, частное получается в нестандартном формате, состоящем из цифр −1 и +1. Этот вид нужно преобразовывать в двоичную форму. Пример: Преобразование частного к цифрам :Старт: 1. Образуем положительный член: 2. Образуем отрицательный член: 3. Вычитаем: : Отрицательный член представлен в бинарном обратном коде, не в дополнительном коде
Если −1 знаки запомнены как нули (0), как в обычном представлении, то является и вычисление тривиально: осуществляет побитное дополнение (бит заменяется на дополнение бита) исходного . Q := Q − bit.bnot(Q) -- Если цифры −1 в Q представлены как нули.
Наконец, частные, вычисляемые этим алгоритмом, всегда нечётные, а остаток R находится в пределах . Например, . Для приведения к положительному остатку делаем один шаг восстановления после того, как приведена из нестандартного вида к стандартному: if R < 0 then Q := Q − 1 R := R + D end if
Истинный остаток равен R >> n. Как и в варианте с восстановлением, младшие биты используются в том же порядке, как образуются биты частного , и имеет смысл использовать единый сдвиг регистра для обоих чисел одновременно.
Деление SRT Деление названо по первым буквам фамилий создателей (Sweeney, Robertson, Tocher). Деление SRT является популярным методом деления во многих микропроцессорах. Деление подобно делению без восстановления, но использует таблицу поиска на основе делимого и делителя для определения цифры частного.
Наиболее существенная разница в том, что используется избыточное представление для частного. Например, если реализуется деление SRT по основанию 4, каждая цифра частного выбирается из пяти возможностей: . Ввиду этого выбор цифры частного не обязательно должен быть точным. Позднее цифры частного можно откорректировать. Например, пары цифр и эквивалентны, поскольку . Это допустимое отклонение позволяет выбирать цифры частного, исходя только из нескольких наиболее значащих бит делимого и делителя вместо вычитания по полной длине. Это упрощение, в свою очередь, позволяет применять для чисел основание больше 2.
Подобно невосстанавливающему делению, конечными шагами являются вычитание по полной длине чисел, чтобы получить последний бит частного, и приведение частного к стандартному двоичному виду.
Печально известный баг плавающего деления в процессорах Intel Pentium был вызван неправильно закодированной таблицей поиска. Пять из 1066 ячеек таблицы были ошибочно опущены.
Методы быстрого деления
Деление Ньютона — Рафсона Деление Ньютона — Рафсона использует метод Ньютона для нахождения обратного к числа и умножает это обратное на , чтобы найти результирующее частное .
Шаги деления Ньютона — Рафсона: Вычисляем приближение для обратного числа делителя . Последовательно вычисляем более точные приближения обратного числа. Это место, где, собственно, и используется метод Ньютона — Рафсона. Вычисляем частное путём умножения делимого на обратное к делителю: .
Чтобы применить метод Ньютона для нахождения обратного к числа, необходимо найти функцию , имеющую нуль в точке . Очевидно, что такой функцией является , но итерации Ньютона — Рафсона для неё неуспешны, поскольку не могут быть осуществлены без знания обратного к числа (более того, метод пытается вычислить точное обратное за один шаг, а не делать итеративные улучшения). Функция, которая работает — это , для которой итерация Ньютона — Рафсона даёт
что можно вычислить из , используя только умножение и вычитание или два умножения-сложения.
С точки зрения вычислений выражения и не эквивалентны. Чтобы получить точность в 2n бит при использовании второго выражения, нужно вычислить произведение между и с двойной точностью к заданной точности (n бит). В отличие от этого произведение и нужно вычислять только с точностью n бит, поскольку ведущие n бит (после двоичной точки) числа нулевые.
Если ошибка определяется как , то
Эта ошибка в квадрате на каждом шаге итерации (так называемая квадратичная сходимость метода Ньютона — Рафсона) имеет эффект такой, что число верных знаков в результате, грубо говоря, удваивается для каждой итерации, свойство, которое становится крайне важным, когда встречающиеся числа имеют много знаков. Но это также означает, что начальная сходимость метода может оказаться сравнительно медленной, особенно если значение выбрано плохо.
Для подзадачи выбора начальной оценки удобно применить сдвиг делителя , чтобы он оказался между , с применением того же самого сдвига к делимому , чтобы частное не изменилось. Тогда можно использовать линейную Аппроксимацию в виде
для инициализации метода Ньютона — Рафсона. Чтобы минимизировать максимальную абсолютную ошибку этого приближения на интервале , следует использовать
Коэффициенты линейного приближения определяются следующим образом. Абсолютное значение ошибки равно . Минимум максимального абсолютного значения ошибки определяется согласно , применённой к . Локальный минимум функции будет в точке, где , что имеет решение . Функция в этом минимуме должна иметь значение с противоположным знаком по отношению к крайним точкам интервала, а именно, . Два равенства от двух неизвестных дают единственное решение и , а максимальная ошибка равна . При использовании этого приближения абсолютное значение ошибки начального значения меньше, чем
Можно образовать многочлен со степенью большей 1, вычислив коэффициенты согласно алгоритму Ремеза. Тогда начальное приближение требует больших вычислений, что может компенсироваться меньшим числом итераций Ньютона — Рафсона.