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

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

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

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

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

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

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

это вход, и

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

это выход.

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

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

R := N
Q := 0
while R ≥ D do
  R := R − D
  Q := Q + 1
end
return (Q,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
  -- At this point, N ≥ 0 and 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                  -- Initialize quotient and remainder to zero
R := 0                     
for i := n − 1 .. 0 do  -- Where n is number of bits in N
  R := R << 1           -- Left-shift R by 1 bit
  R(0) := N(i)          -- Set the least-significant bit of R equal to bit i of the numerator
  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.

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

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

$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 and D need twice the word width of N and Q
for i := n − 1 .. 0 do  -- For example 31..0 for 32 bits
  R := 2 * R − D          -- Trial subtraction from shifted value (multiplication by 2 is a shift in binary representation)
  if R >= 0 then
    q(i) := 1          -- Result-bit 1
  else
    q(i) := 0          -- Result-bit 0
    R := R + D         -- New partial remainder is (restored) shifted value
  end
end

-- Where: N = numerator, D = denominator, n = #bits, R = partial remainder, q(i) = bit #i of quotient

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

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

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

R := N
D := D << n            -- R and D need twice the word width of N and Q
for i = n − 1 .. 0 do  -- for example 31..0 for 32 bits
  if R >= 0 then
    q(i) := +1
    R := 2 * R − D
  else
    q(i) := −1
    R := 2 * R + D
  end if
end
 
-- Note: N=numerator, D=denominator, n=#bits, R=partial remainder, q(i)=bit #i of quotient.

Следуя этому алгоритму, частное имеет нестандартную форму, состоящую из цифр -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 − bit.bnot(Q)      -- Appropriate if −1 digits in Q are represented as zeros as is common.

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

if R < 0 then
  Q := Q − 1
  R := R + D  -- Needed only if the remainder is of interest.
end if

Фактический остаток равен 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 двоичных разрядов:

Express D as M × 2e where 1 ≤ M < 2 (standard floating point representation)
D' := D / 2e+1   // scale between 0.5 and 1, can be performed with bit shift / exponent subtraction
N' := N / 2e+1
X := 48/17 − 32/17 × D'   // precompute constants with same precision as D
repeat $\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,$ times   // can be precomputed based on fixed P
    X := X + X × (1 - D' × X)
end
return 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 г.