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

Эта статья об алгоритмах деления целых чисел. Информацию об алгоритме «карандаш и бумага» см. в разделе «Деление в столбик» . Алгоритм деления полиномов см. в разделе Полиномиальное деление в длину .

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

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

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

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

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

это вход, и

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

это выход.

Деление повторным вычитанием

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

R   :  =   N 
 Q   :  =   0 
 в то время как   R   ≥   D   do 
   R   :  =   R   -   D 
   Q   :  =   Q   +   1 
 конец 
 возврата   (  Q  ,  R  ) 

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

функция   делить  (  N  ,   D  ) 
   , если   D   =   0   , то   ошибка  (  DivisionByZero  )   заканчивается, 
   если   D   <   0   , то   (  Q  ,   R  )   :  =   делить  (  N  ,   −  D  );    return   (  -  Q  ,   R  )   конец, 
   если   N   <   0   , то 
     (  Q  ,  R  )   :  =   деление  (  -  N  ,   D  ) 
     если   R   =   0   , то   возврат   (  -  Q  ,   0  ) 
     иначе   возврат   (  -  Q   -   1  ,   D   -   R  )   end 
   end 
   -- В этот момент N ≥ 0 и D > 0 
   возвращают   div_unsigned  (  N  ,   D  ) 
 end   
 функция   div_unsigned  (  N  ,   D  ) 
   Q   :  =   0  ;    R   :  =   N 
   в то время как   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 числителя, 
   если   R   ≥   D   , то 
     R   :  =   R   −   D 
     Q  (  я  )   :  =   1 
   конец 
 конец 

Пример

Если взять 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.

Методы медленного деления

Все методы медленного деления основаны на стандартном рекуррентном уравнении.

$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 
 для   i   :  =   n   −   1   ..   0   do    -- Например 31..0 для 32 битов 
   R   :  =   2   *   R   −   D            — Пробное вычитание из сдвинутого значения (умножение на 2 — это сдвиг в двоичном представлении), 
   если   R   >=   0   , то 
     q  (  i  )   :  =   1            — Бит результата 1 
   else 
     q  (  i  )   :  =   0            -- Бит результата 0 
     R   :  =   R   +   D           -- Новый частичный остаток представляет собой (восстановленный) сдвинутый конец значения 
   -- 
 Где 

 : N = числитель, D = знаменатель, n = #биты, R = частичный остаток, q(i ) = бит #i частного 

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

Невосстанавливающееся деление

Деление без восстановления использует набор цифр {-1, 1} для цифр частного вместо {0, 1}. Алгоритм более сложен, но при аппаратной реализации имеет то преимущество, что для каждого бита частного требуется только одно решение и сложение/вычитание; после вычитания нет этапа восстановления, что потенциально сокращает количество операций почти вдвое и позволяет выполнять их быстрее. Основной алгоритм двоичного (основание 2) невосстанавливающегося деления неотрицательных чисел:

R   :  =   N 
 D   :  =   D   <<   n              -- R и D требуется удвоенная ширина слова N и Q 
 для   i   =   n   −   1   ..   0   do    -- например 31..0 для 32 бит, 
   если   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}:
Начинать:	$Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}$
1. Образуйте положительный член:	$P=11101010\,$
2. Замаскируйте отрицательный термин*:	$M=00010101\,$
3. Вычтите: $P-M$:	$Q=11010101\,$
*.(Знаковая двоичная запись с дополнением до единиц без дополнения до двух )

Если -1 цифры $Q$ хранятся как нули (0), как обычно, тогда $P$ является $Q$ и вычисления $M$ тривиально: выполнить дополнение единиц (побитовое дополнение) к оригиналу $Q$.

Q   :  =   Q   -   бит  .   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 — популярный метод деления во многих реализациях микропроцессоров . Алгоритм назван в честь Д. У. Суини из IBM , Джеймса Э. Робертсона из Университета Иллинойса и К. Д. Точера из Имперского колледжа Лондона . Все они разработали алгоритм независимо друг от друга примерно в одно и то же время (опубликовано в феврале 1957 г., сентябре 1958 г. и январе 1958 г. соответственно).

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

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

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

Intel Pentium в процессоре Печально известная ошибка деления чисел с плавающей запятой была вызвана неправильно закодированной справочной таблицей. Пять из 1066 записей были ошибочно пропущены.

Методы быстрого деления

Разделение Ньютона-Рафсона

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

Этапы разделения Ньютона-Рафсона:

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

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

$$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}),$$

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

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

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

${\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}}$

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

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

$X_{0}=T_{1}+T_{2}D\approx {\frac {1}{D}}\,$

для инициализации Ньютона-Рафсона. Минимизировать максимум абсолютного значения ошибки данного приближения на интервале $[0.5,1]$, следует использовать

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

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

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

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

Поскольку для этого метода сходимость в точности квадратичная, отсюда следует, что

$S=\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,$

шагов достаточно, чтобы вычислить значение до $P\,$бинарные места. Это значение равно 3 для форматов одинарной точности IEEE и 4 для форматов двойной точности и расширенного формата двойной точности .

Псевдокод

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

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

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

Ньютона-

Метод деления Ньютона-Рафсона можно изменить, чтобы он стал немного быстрее, следующим образом. После сдвига N и D так, чтобы D находился в [0,5, 1,0], инициализируйте с помощью

$X:={\frac {140}{33}}+D\cdot \left({\frac {-64}{11}}+D\cdot {\frac {256}{99}}\right).$

Это наилучшее квадратичное приближение к 1/ D , которое дает абсолютное значение ошибки меньше или равное 1/99. Ошибка выбрана так, чтобы ошибка была равна перемасштабированному полиному Чебышева третьего порядка первого рода. Коэффициенты должны быть заранее рассчитаны и жестко закодированы.

Затем в цикле используйте итерацию, которая кубизирует ошибку.

$E:=1-D\cdot X$

$Y:=X\cdot E$

$X:=X+Y+Y\cdot E.$

Термин Y ⋅ E является новым.

Если цикл выполняется до тех пор, пока X не согласуется с 1/ D на своих ведущих битах P , то количество итераций будет не более

$\left\lceil \log _{3}\left({\frac {P+1}{\log _{2}99}}\right)\right\rceil$

сколько раз 99 нужно возложить в куб, чтобы получить 2 ^{П +1} . Затем

$Q:=N\cdot X$

это частное к P битам.

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

Подразделение Гольдшмидта

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

$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, каждый F _i основан на D :

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

Умножение дивиденда и делителя на коэффициент дает:

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

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

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

Биномиальная

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

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

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

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

Методы больших целых чисел

Методы, предназначенные для аппаратной реализации, обычно не масштабируются до целых чисел с тысячами или миллионами десятичных цифр; они часто возникают, например, при модульном сокращении криптографии . Для этих больших целых чисел более эффективные алгоритмы деления преобразуют задачу, используя небольшое количество умножений, что затем можно выполнить с помощью асимптотически эффективного алгоритма умножения , такого как алгоритм Карацубы , умножение Тума-Кука или алгоритм Шёнхаге-Штрассена . В результате вычислительная сложность деления имеет тот же порядок (с точностью до мультипликативной константы), что и умножение. Примеры включают приведение к умножению методом Ньютона , как описано выше , а также немного более быстрая дивизия Бурникеля-Циглера , редукции Барретта и редукции Монтгомери . Алгоритмы Метод Ньютона особенно эффективен в сценариях, где необходимо многократно делить на один и тот же делитель, поскольку после первоначального обращения Ньютона для каждого деления требуется только одно (усеченное) умножение.

Деление на константу

Деление на константу D эквивалентно умножению на обратную величину . Поскольку знаменатель постоянен, то и его обратная величина (1/ D ) постоянна. Таким образом, можно вычислить значение (1/ D ) один раз во время компиляции, а во время выполнения выполнить умножение N ·(1/ D ), а не деление N/D . В арифметике с плавающей запятой использование (1/ D ) не представляет особых проблем. но в целочисленной арифметике обратная величина всегда будет равна нулю (при условии | 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 , но «достаточно близко», чтобы ошибка, вносимая аппроксимацией, составляла в битах, которые отбрасываются в результате операции сдвига. Сокращение Барретта использует степени 2 для значения Y , чтобы сделать деление на Y простым сдвигом вправо.

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

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

$\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$

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

Ошибка округления

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

Дополнительная информация: Плавающая точка.

См. также

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

Дальнейшее чтение

• Савард, Джон Дж. Г. (2018) [2006]. «Продвинутые арифметические методы» . четырехблок . Архивировано из оригинала 3 июля 2018 г. Проверено 16 июля 2018 г.