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

Алгоритм деления — это алгоритм , который, имея два целых числа N и D (соответственно числитель и знаменатель), вычисляет их частное и/или остаток , результат евклидова деления . Некоторые из них применяются вручную, в то время как другие используются цифровыми схемами и программным обеспечением.

Алгоритмы деления делятся на две основные категории: медленное деление и быстрое деление. Медленные алгоритмы деления производят одну цифру конечного частного за итерацию. Примерами медленного деления являются восстанавливающее, непроизводительное восстанавливающее, невосстанавливающее и SRT-деление. Быстрые методы деления начинаются с близкого приближения к конечному частному и производят вдвое больше цифр конечного частного за каждую итерацию. ^[1] Алгоритмы Ньютона-Рафсона и Гольдшмидта попадают в эту категорию.

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

Обсуждение будет относиться к форме , где${\displaystyle N/D=(Q,R)}$

• N = числитель (делимое)
• D = знаменатель (делитель)

является входом, и

• Q = частное
• Р = остаток

это выход.

Простейший алгоритм деления, исторически включенный в алгоритм нахождения наибольшего общего делителя , представленный в «Началах » Евклида , Книга VII, Предложение 1, находит остаток для двух данных положительных целых чисел, используя только вычитания и сравнения:

R  : =  N Q  : =  0 пока  R  ≥  D  сделать  R  : =  R  −  D  Q  : =  Q  +  1 конец вернуть  ( Q , R )

Доказательство того, что частное и остаток существуют и являются уникальными (описано в разделе Евклидово деление ), приводит к полному алгоритму деления, применимому как к отрицательным, так и к положительным числам, с использованием сложений, вычитаний и сравнений:

function  divide ( N ,  D )  if  D  =  0  then  error ( DivisionByZero )  end  if  D  <  0  then  ( Q ,  R )  : =  divided ( N ,  −D ) ; return ( −Q , R ) end if N < 0 then ( Q , R ) : = divided ( −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                                                               

Эта процедура всегда производит R ≥ 0. Хотя она очень проста, она занимает Ω(Q) шагов, и поэтому экспоненциально медленнее, чем даже медленные алгоритмы деления, такие как длинное деление. Она полезна, если известно, что Q мало (будучи чувствительным к выходу алгоритмом ), и может служить исполняемой спецификацией.

Длинное деление — стандартный алгоритм, используемый для деления с помощью ручки и бумаги многозначных чисел, выраженных в десятичной системе счисления. Он постепенно смещается от левого к правому концу делимого, вычитая на каждом этапе максимально возможное кратное делителя (на уровне цифр); затем кратные становятся цифрами частного, а конечная разность — остатком.

При использовании с двоичным основанием этот метод формирует основу для алгоритма (беззнакового) целочисленного деления с остатком ниже. Короткое деление — это сокращенная форма длинного деления, подходящая для однозначных делителей. Разделение на части  — также известное как метод частичных частных или метод палача — это менее эффективная форма длинного деления, которая может быть более простой для понимания. Позволяя вычитать больше кратных, чем есть в данный момент на каждом этапе, можно также разработать более свободный вариант длинного деления.

Следующий алгоритм, двоичная версия знаменитого деления в столбик , разделит N на D , поместив частное в Q , а остаток в R. В следующем псевдокоде все значения рассматриваются как целые числа без знака.

if  D  =  0  then  error ( DivisionByZeroException )  end Q  : =  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

Если мы возьмем N=1100 ₂ (12 ₁₀ ) и D=100 ₂ (4 ₁₀ )

Шаг 1 : Устанавливаем R=0 и Q=0.
Шаг 2 : Берем i=3 (на единицу меньше числа бит в N).
Шаг 3 : R=00 (сдвиг влево на 1).
Шаг 4 : R=01 (устанавливаем R(0) на N(i))
Шаг 5 : R < D, поэтому пропускаем оператор.

Шаг 2 : Установить i=2
Шаг 3 : R=010
Шаг 4 : R=011
Шаг 5 : R < D, оператор пропущен

Шаг 2 : Установить i=1
Шаг 3 : R=0110
Шаг 4 : R=0110
Шаг 5 : R>=D, введено утверждение
Шаг 5b : R=10 (R−D)
Шаг 5c : Q=10 (устанавливаем Q(i) в 1)

Шаг 2 : Установить i=0
Шаг 3 : R=100
Шаг 4 : R=100
Шаг 5 : R>=D, введено утверждение
Шаг 5b : R=0 (R−D)
Шаг 5c : Q=11 (устанавливаем Q(i) в 1)

конец
Q=11 ₂ (3 ₁₀ ) и R=0.

Все методы медленного деления основаны на стандартном рекуррентном уравнении ^[2]

${\displaystyle R_{j+1}=B\times R_{j}-q_{n-(j+1)}\times D,}$

где:

• R _j — это j -й частичный остаток от деления
• B — основание системы счисления (в компьютерах и калькуляторах обычно 2)
• q _{n − ( j + 1)} — цифра частного в позиции n −( j +1), где позиции цифр пронумерованы от наименее значащего 0 до наиболее значащего n −1
• n — количество цифр в частном
• D — делитель

Восстановление деления выполняется над дробными числами с фиксированной точкой и зависит от предположения 0 < D < N. ^{[ необходима ссылка ]}

Цифры частного q образуются из набора цифр {0,1}.

Базовый алгоритм восстановления двоичного (основание 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 частного

Невыполняемое восстанавливающее деление похоже на восстанавливающее деление, за исключением того, что значение 2R сохраняется, поэтому D не нужно добавлять обратно в случае R < 0.

Невосстанавливающее деление использует набор цифр {−1, 1} для цифр частного вместо {0, 1}. Алгоритм более сложен, но имеет преимущество при реализации на аппаратном уровне, так как на каждый бит частного приходится только одно решение и сложение/вычитание; после вычитания нет восстанавливающего шага, ^[3] что потенциально сокращает количество операций до половины и позволяет выполнять его быстрее. ^[4] Базовый алгоритм для двоичного (основание 2) невосстанавливающего деления неотрицательных чисел: ^{[ требуется проверка ]}

R  : =  N D  : =  D  <<  n  -- R и D требуют удвоенную ширину слова N и Q для  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. Эту форму необходимо преобразовать в двоичную, чтобы сформировать окончательное частное. Пример:

Преобразуем следующее частное в набор цифр {0,1}:
Начинать:	${\displaystyle Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}}$
1. Образуйте положительный член:	${\displaystyle P=11101010\,}$
2. Замаскируйте отрицательный термин: [примечание 1]	${\displaystyle М=00010101\,}$
3. Вычесть: :${\displaystyle PM}$	${\displaystyle Q=11010101\,}$
^ Знаковая двоичная запись с дополнением до единицы без дополнения до двух .

Если цифры −1 хранятся как нули (0), как это обычно бывает, то и вычисление тривиально: выполнить дополнение до единиц (побитовое дополнение) исходного числа .${\displaystyle Q}$${\displaystyle P}$ ${\displaystyle Q}$${\displaystyle М}$${\displaystyle Q}$

Q  : =  Q  −  bit . bnot ( Q )  — Подходит, если −1 цифр в Q представлены в виде нулей, как это часто бывает.

Наконец, частные, вычисленные этим алгоритмом, всегда нечетные, а остаток в R находится в диапазоне −D ≤ R < D. Например, 5 / 2 = 3 R −1. Чтобы преобразовать в положительный остаток, выполните один шаг восстановления после преобразования Q из нестандартной формы в стандартную:

если  R  <  0,  то  Q  : =  Q  −  1  R  : =  R  +  D  -- Требуется только если остаток представляет интерес. конец  если

Фактический остаток равен R >> n. (Как и при восстанавливающем делении, младшие биты R используются с той же скоростью, с которой производятся биты частного Q, и для обоих случаев обычно используется один регистр сдвига.)

SRT-деление — популярный метод деления во многих реализациях микропроцессоров . ^{[5] [6]} Алгоритм назван в честь DW Sweeney из IBM , James E. Robertson из Университета Иллинойса и KD Tocher из Имперского колледжа Лондона . Они все разработали алгоритм независимо друг от друга примерно в одно и то же время (опубликован в феврале 1957, сентябре 1958 и январе 1958 соответственно). ^{[7] [8] [9]}

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

Наиболее существенное отличие заключается в том, что для частного используется избыточное представление . Например, при реализации деления SRT по основанию 4 каждая цифра частного выбирается из пяти возможных: { −2, −1, 0, +1, +2 }. Из-за этого выбор цифры частного не обязательно должен быть идеальным; последующие цифры частного могут корректировать небольшие ошибки. (Например, пары цифр частного (0, +2) и (1, −2) эквивалентны, поскольку 0×4+2 = 1×4−2.) Этот допуск позволяет выбирать цифры частного, используя только несколько старших бит делимого и делителя, вместо того, чтобы требовать вычитания полной ширины. Это упрощение, в свою очередь, позволяет использовать основание выше 2.

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

Печально известная ошибка деления с плавающей точкой процессора Intel Pentium была вызвана неправильно закодированной таблицей поиска. Пять из 1066 записей были ошибочно пропущены. ^{[10] [11] [12]}

Ньютон-Рафсон использует метод Ньютона для нахождения обратной величины и умножает эту обратную величину на , чтобы найти окончательное частное .${\displaystyle D}$${\displaystyle N}$${\displaystyle Q}$

Шаги деления Ньютона-Рафсона следующие:

1. Рассчитайте оценку обратной величины делителя .${\displaystyle X_{0}}$${\displaystyle 1/D}$${\displaystyle D}$
2. Вычислить последовательно более точные оценки обратной величины. Здесь используется метод Ньютона–Рафсона как таковой.${\displaystyle X_{1},X_{2},\ldots ,X_{S}}$
3. Вычислите частное, умножив делимое на величину, обратную делителю: .${\displaystyle Q=NX_{S}}$

Чтобы применить метод Ньютона для нахождения обратной величины , необходимо найти функцию , которая имеет ноль в точке . Очевидно, что такой функцией является , но итерация Ньютона–Рафсона для этого бесполезна, поскольку ее нельзя вычислить, не зная уже обратной величины (более того, она пытается вычислить точную обратную величину за один шаг, а не допускает итерационных улучшений). Функция, которая действительно работает, это , для которой итерация Ньютона–Рафсона дает${\displaystyle D}$${\displaystyle f(X)}$${\displaystyle X=1/D}$${\displaystyle f(X)=DX-1}$${\displaystyle D}$${\displaystyle f(X)=(1/X)-D}$

$${\displaystyle X_{i+1}=X_{i}-{f(X_{i}) \over f'(X_{i})}=X_{i}-{1/X_{i}-D \over -1/X_{i}^{2}}=X_{i}+X_{i}(1-DX_{i})=X_{i}(2-DX_{i}),}$$

который можно вычислить, используя только умножение и вычитание, или используя два объединенных умножения-сложения .${\displaystyle X_{i}}$

С точки зрения вычислений выражения и не эквивалентны. Чтобы получить результат с точностью 2 n бит, используя второе выражение, необходимо вычислить произведение между и с удвоенной заданной точностью ( n бит). ^{[ необходима цитата ]} Напротив, произведение между и нужно вычислить только с точностью n бит, поскольку первые n бит (после двоичной точки) являются нулями.${\displaystyle X_{i+1}=X_{i}+X_{i}(1-DX_{i})}$${\displaystyle X_{i+1}=X_{i}(2-DX_{i})}$${\displaystyle X_{i}}$${\displaystyle (2-DX_{i})}$${\displaystyle X_{i}}$${\displaystyle X_{i}}$${\displaystyle (1-DX_{i})}$${\displaystyle (1-DX_{i})}$

Если ошибка определена как , то:${\displaystyle \varepsilon _{i}=1-DX_{i}}$

${\displaystyle {\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-D(X_{i}(2-DX_{i}))\\&=1-2DX_{i}+D^{2}X_{i}^{2}\\&=(1-DX_{i})^{2}\\&={\varepsilon _{i}}^{2}.\\\end{aligned}}}$

Это возведение ошибки в квадрат на каждом шаге итерации — так называемая квадратичная сходимость метода Ньютона–Рафсона — приводит к тому, что количество правильных цифр в результате примерно удваивается для каждой итерации , свойство, которое становится чрезвычайно ценным, когда задействованные числа имеют много цифр (например, в большой целочисленной области). Но это также означает, что начальная сходимость метода может быть сравнительно медленной, особенно если начальная оценка выбрана неудачно.${\displaystyle X_{0}}$

Для подзадачи выбора начальной оценки удобно применить битовый сдвиг к делителю D , чтобы масштабировать его так, чтобы 0,5 ≤  D  ≤ 1. Применение того же битового сдвига к числителю N гарантирует, что частное не изменится. Оказавшись в ограниченном диапазоне, можно использовать простую полиномиальную аппроксимацию для нахождения начальной оценки.${\displaystyle X_{0}}$

Линейное приближение с минимальной абсолютной ошибкой в ​​худшем случае на интервале имеет вид:${\displaystyle [0.5,1]}$

${\displaystyle X_{0}={48 \over 17}-{32 \over 17}D.}$

Коэффициенты линейного приближения определяются следующим образом. Абсолютное значение погрешности равно . Минимум максимального абсолютного значения погрешности определяется теоремой Чебышева о равноколебаниях, примененной к . Локальный минимум достигается при , который имеет решение . Функция в этом минимуме должна иметь противоположный знак, как и функция в конечных точках, а именно, . Два уравнения с двумя неизвестными имеют единственное решение и , а максимальная погрешность равна . Используя это приближение, абсолютное значение погрешности начального значения меньше${\displaystyle T_{0}+T_{1}D}$${\displaystyle |\varepsilon _{0}|=|1-D(T_{0}+T_{1}D)|}$${\displaystyle F(D)=1-D(T_{0}+T_{1}D)}$${\displaystyle F(D)}$${\displaystyle F'(D)=0}$${\displaystyle D=-T_{0}/(2T_{1})}$${\displaystyle F(1/2)=F(1)=-F(-T_{0}/(2T_{1}))}$${\displaystyle T_{0}=48/17}$${\displaystyle T_{1}=-32/17}$${\displaystyle F(1)=1/17}$

${\displaystyle \vert \varepsilon _{0}\vert \leq {1 \over 17}\approx 0.059.}$

Наилучшее квадратичное приближение в интервале равно${\displaystyle 1/D}$

${\displaystyle X:={\frac {140}{33}}-{\frac {64}{11}}D+{\frac {256}{99}}D^{2}.}$

Он выбран так, чтобы сделать ошибку равной перемасштабированному полиному Чебышева третьего порядка первого рода, и дает абсолютное значение ошибки меньше или равное 1/99. Это улучшение эквивалентно итерациям Ньютона-Рафсона при вычислительных затратах менее одной итерации.${\displaystyle \log _{2}(\log 99/\log 17)\approx 0.7}$

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

Поскольку для этого метода сходимость точно квадратичная, то из начальной ошибки следует, что итерации дадут ответ с точностью до${\displaystyle \varepsilon _{0}}$${\displaystyle S}$

${\displaystyle P=-2^{S}\log _{2}\varepsilon _{0}-1=2^{S}\log _{2}(1/\varepsilon _{0})-1}$

Двоичные места. Типичные значения:

Двоичные цифры обратной точности

${\displaystyle \varepsilon _{0}}$	Итерации
	0	1	2	3	4
${\displaystyle 1/17}$	3.09	7.17	15.35	31.70	64.40
${\displaystyle 1/99}$	5.63	12.26	25.52	52.03	105.07

Квадратичная начальная оценка плюс две итерации достаточно точны для IEEE single precision , но три итерации являются маргинальными для double precision . Линейная начальная оценка плюс четыре итерации достаточны как для double, так и для double extended форматов.

Следующий код вычисляет частное N и D с точностью до P двоичных знаков:

Выразите D как M × 2 e , где 1 ≤ M < 2 (стандартное представление с плавающей точкой)D' := D / 2 e+1  // масштаб от 0,5 до 1, может быть выполнен с помощью битового сдвига / вычитания экспоненты
N' := N / 2 e+1
X := 48/17 − 32/17 × D' // предварительно вычислить константы с той же точностью, что и D повторить  раз${\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}$   // можно предварительно вычислить на основе фиксированного P X := X + X × (1 - D' × X)конец возврата N' × X

Например, для деления чисел с плавающей запятой двойной точности этот метод использует 10 умножений, 9 сложений и 2 сдвига.

Существует итерация, которая использует три умножения для возведения ошибки в куб:

${\displaystyle \varepsilon _{i}=1-DX_{i}}$

${\displaystyle Y_{i}=X_{i}\varepsilon _{i}}$

${\displaystyle X_{i+1}=X_{i}+Y_{i}+Y_{i}\varepsilon _{i}.}$

Термин Y _i ε _i является новым.

Расширяя вышесказанное, можно записать как${\displaystyle X_{i+1}}$

${\displaystyle {\begin{aligned}X_{i+1}&=X_{i}+X_{i}\varepsilon _{i}+X_{i}\varepsilon _{i}^{2}\\&=X_{i}+X_{i}(1-DX_{i})+X_{i}(1-DX_{i})^{2}\\&=3X_{i}-3DX_{i}^{2}+D^{2}X_{i}^{3},\end{aligned}}}$

в результате чего ошибка

${\displaystyle {\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-3DX_{i}+3D^{2}X_{i}^{2}-D^{3}X_{i}^{3}\\&=(1-DX_{i})^{3}\\&=\varepsilon _{i}^{3}.\end{aligned}}}$

Это 3/2 вычисления квадратичной итерации, но достигает такой же сходимости, поэтому немного эффективнее. Другими словами, две итерации этого метода увеличивают ошибку до девятой степени при тех же вычислительных затратах, что и три квадратичные итерации, которые увеличивают ошибку только до восьмой степени.${\displaystyle \log 3/\log 2\approx 1.585}$

Количество правильных бит после итераций равно${\displaystyle S}$

${\displaystyle P=-3^{S}\log _{2}\varepsilon _{0}-1=3^{S}\log _{2}(1/\varepsilon _{0})-1}$

Двоичные места. Типичные значения:

Частицы взаимной точности

${\displaystyle \varepsilon _{0}}$	Итерации
	0	1	2	3
${\displaystyle 1/17}$	3.09	11.26	35.79	109.36
${\displaystyle 1/99}$	5.63	18.89	58.66	177.99

Квадратичная начальная оценка плюс две кубические итерации обеспечивают достаточную точность для результата двойной точности IEEE. Также возможно использовать смесь квадратичных и кубических итераций.

Использование хотя бы одной квадратичной итерации гарантирует, что ошибка будет положительной, т.е. обратная величина будет занижена. ^{[13] : 370} Это может упростить следующий шаг округления, если требуется точно округленное частное.

Использование полиномов более высокой степени как при инициализации, так и при итерации приводит к снижению производительности, поскольку дополнительные требуемые умножения лучше потратить на выполнение большего количества итераций. ^{[ необходима ссылка ]}

Деление Гольдшмидта ^[14] (в честь Роберта Эллиота Гольдшмидта) ^[15] использует итеративный процесс многократного умножения делимого и делителя на общий множитель F _i , выбранный таким образом, чтобы делитель сходился к 1. Это приводит к тому, что делимое сходится к искомому частному Q :

${\displaystyle Q={\frac {N}{D}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots }}{F_{\ldots }}}.}$

Шаги для разделения Гольдшмидта следующие:

1. Сгенерируйте оценку коэффициента умножения F _i .
2. Умножьте делимое и делитель на F _i .
3. Если делитель достаточно близок к 1, вернуть делимое, в противном случае вернуться к шагу 1.

Предполагая, что _N / D масштабируется таким образом, что 0 <  D  < 1, каждый Fi основан на D :

${\displaystyle F_{i+1}=2-D_{i}.}$

Умножение делимого и делителя на множитель дает:

${\displaystyle {\frac {N_{i+1}}{D_{i+1}}}={\frac {N_{i}}{D_{i}}}{\frac {F_{i+1}}{F_{i+1}}}.}$

После достаточного количества k итераций .${\displaystyle Q=N_{k}}$

Метод Гольдшмидта используется в процессорах AMD Athlon и более поздних моделях. ^{[16] [17]} Он также известен как алгоритм Андерсона Эрла Голдшмидта Пауэрса (AEGP) и реализован различными процессорами IBM. ^{[18] [19]} Хотя он сходится с той же скоростью, что и реализация Ньютона-Рафсона, одним из преимуществ метода Гольдшмидта является то, что умножения в числителе и знаменателе могут выполняться параллельно. ^[19]

Метод Гольдшмидта можно использовать с факторами, которые допускают упрощения по биномиальной теореме . Предположим, что ⁠ ⁠${\displaystyle N/D}$ масштабируется по степени двойки таким образом, что . Мы выбираем и . Это дает${\displaystyle D\in \left({\tfrac {1}{2}},1\right]}$${\displaystyle D=1-x}$${\displaystyle F_{i}=1+x^{2^{i}}}$

$${\displaystyle {\frac {N}{1-x}}={\frac {N\cdot (1+x)}{1-x^{2}}}={\frac {N\cdot (1+x)\cdot (1+x^{2})}{1-x^{4}}}=\cdots =Q'={\frac {N'=N\cdot (1+x)\cdot (1+x^{2})\cdot \cdot \cdot (1+x^{2^{(n-1)}})}{D'=1-x^{2^{n}}\approx 1}}}$$.

После n шагов знаменатель можно округлить до${\displaystyle \left(x\in \left[0,{\tfrac {1}{2}}\right)\right)}$${\displaystyle 1-x^{2^{n}}}$1 с относительной погрешностью

${\displaystyle \varepsilon _{n}={\frac {Q'-N'}{Q'}}=x^{2^{n}}}$

что максимально при , обеспечивая тем самым минимальную точность двоичных цифр.${\displaystyle 2^{-2^{n}}}$${\displaystyle x={\tfrac {1}{2}}}$${\displaystyle 2^{n}}$

Методы, разработанные для аппаратной реализации, обычно не масштабируются до целых чисел с тысячами или миллионами десятичных цифр; это часто происходит, например, при модульных сокращениях в криптографии . Для этих больших целых чисел более эффективные алгоритмы деления преобразуют задачу для использования небольшого количества умножений, что затем может быть выполнено с помощью асимптотически эффективного алгоритма умножения, такого как алгоритм Карацубы , умножение Тоома–Кука или алгоритм Шёнхаге–Штрассена . Результатом является то, что вычислительная сложность деления имеет тот же порядок (с точностью до мультипликативной константы), что и умножение. Примерами являются сведение к умножению методом Ньютона , как описано выше, ^[20] , а также немного более быстрое деление Бурникеля–Циглера, ^[21] алгоритмы сокращения Барретта и сокращения Монтгомери . ^{[22] [ требуется проверка ]} Метод Ньютона особенно эффективен в сценариях, где необходимо делить на один и тот же делитель много раз, поскольку после первоначального обращения Ньютона для каждого деления требуется только одно (усеченное) умножение.

Деление на константу D эквивалентно умножению на ее обратную величину . Поскольку знаменатель является константой, то и ее обратная величина (1/ D ) является константой. Таким образом, можно вычислить значение (1/ D ) один раз во время компиляции, а во время выполнения выполнить умножение N ·(1/ D ) вместо деления N/D . В арифметике с плавающей точкой использование (1/ D ) представляет небольшую проблему, ^[a] но в целочисленной арифметике обратная величина всегда будет равна нулю (предполагая, что | D | > 1).

Не обязательно использовать конкретно (1/ D ); можно использовать любое значение ( X / Y ), которое сводится к (1/ D ). Например, для деления на 3 можно использовать множители 1/3, 2/6, 3/9 или 194/582. Следовательно, если бы Y был степенью двойки, шаг деления свелся бы к быстрому сдвигу бита вправо. Эффект вычисления N / D как ( N · X )/ Y заменяет деление умножением и сдвигом. Обратите внимание, что скобки важны, так как N ·( X / Y ) будет оцениваться как ноль.

Однако, если только D сам по себе не является степенью двойки, то не существует X и Y , которые удовлетворяют приведенным выше условиям. К счастью, ( N · X )/ Y дает точно такой же результат, как N / D в целочисленной арифметике, даже когда ( X / Y ) не точно равно 1/ D , но «достаточно близко», чтобы ошибка, вносимая приближением, была в битах, которые отбрасываются операцией сдвига. ^{[23] [24] [25]} Редукция Барретта использует степени 2 для значения Y , чтобы сделать деление на Y простым сдвигом вправо. ^[b]

В качестве конкретного примера арифметики с фиксированной точкой для 32-битных беззнаковых целых чисел деление на 3 можно заменить умножением на ⁠2863311531/2 ³³⁠ , умножение на 2863311531 ( шестнадцатеричное 0xAAAAAAAB) с последующим сдвигом вправо на 33 бита. Значение 2863311531 вычисляется как ⁠2 ³³/3⁠ , затем округляется вверх. Аналогично, деление на 10 может быть выражено как умножение на 3435973837 (0xCCCD) с последующим делением на 2 ³⁵ (или 35 правый битовый сдвиг). ^{[27] : стр. 230-234} OEIS предоставляет последовательности констант для умножения как A346495 и для правого сдвига как A346496.

Для общего деления x -битных беззнаковых целых чисел, где делитель D не является степенью числа 2, следующее тождество преобразует деление в два x -битных сложения/вычитания, одно x -битное умножение на x -битное (где используется только верхняя половина результата) и несколько сдвигов после предварительного вычисления и :${\displaystyle k=x+\lceil \log _{2}{D}\rceil }$${\displaystyle a=\left\lceil {\frac {2^{k}}{D}}\right\rceil -2^{x}}$

${\displaystyle \left\lfloor {\frac {N}{D}}\right\rfloor =\left\lfloor {\frac {\left\lfloor {\frac {N-b}{2}}\right\rfloor +b}{2^{k-x-1}}}\right\rfloor {\text{ where }}b=\left\lfloor {\frac {Na}{2^{x}}}\right\rfloor }$

В некоторых случаях деление на константу можно выполнить за еще меньшее время, преобразовав «умножение на константу» в ряд сдвигов и сложений или вычитаний . ^[28] Особый интерес представляет деление на 10, для которого получается точное частное с остатком, если требуется. ^[29]

This section needs expansion. You can help by adding to it. (September 2012)

Когда выполняется операция деления, точное частное и остаток аппроксимируются, чтобы соответствовать пределам точности компьютера. Алгоритм деления гласит:${\displaystyle q}$ ${\displaystyle r}$

${\displaystyle [a=bq+r]}$

где .${\displaystyle 0\leq r<|b|}$

В арифметике с плавающей точкой частное представляется как , а остаток как , что приводит к ошибкам округления и :${\displaystyle q}$${\displaystyle {\tilde {q}}}$${\displaystyle r}$${\displaystyle {\tilde {r}}}$ ${\displaystyle \epsilon _{q}}$${\displaystyle \epsilon _{q}}$${\displaystyle \epsilon _{r}}$

${\displaystyle [{\tilde {q}}=q+\epsilon _{q}][{\tilde {r}}=r+\epsilon _{r}]}$

Это округление вызывает небольшую ошибку, которая может распространяться и накапливаться в ходе последующих вычислений. Такие ошибки особенно выражены в итеративных процессах и при вычитании почти равных значений - говорят о потере значимости . Чтобы смягчить эти ошибки, применяются такие методы, как использование защитных цифр или арифметики более высокой точности. ^{[30] [31]}

• Отделение галеры
• Алгоритм умножения
• Ошибка Pentium FDIV

• Savard, John JG (2018) [2006]. "Advanced Arithmetic Techniques". quadibloc . Архивировано из оригинала 2018-07-03 . Получено 2018-07-16 .