Русская Википедия:Алгоритм деления

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

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

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

Обсуждение будет использовать обозначения <math>N/D = (Q, R)</math>, где

<math>N</math> — числитель (делимое)
<math>D</math> — знаменатель (делитель)

являются входными числами, а

<math>Q</math> — частное
<math>R</math> — остаток

являются выходными данными.

Деление путём вычитаний

Простейший алгоритм, исторически встроенный в алгоритм поиска наибольшего общего делителя и представленный в Началах Евклида, Книга 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

Эта процедура всегда даёт <math>R\geqslant 0</math>. Будучи очень простым, алгоритм требует <math>\Omega(Q)</math> шагов, а потому экспоненциально медленнее, чем алгоритмы наподобие длинного деления. Алгоритм полезен, если известно, что <math>Q</math>(шагов) мало (будучи зависимым от объёма вывода).

Деление столбиком

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

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

Деление целых чисел (без знака) с остатком

Шаблон:Основная статья Приведённый алгоритм, двоичная версия известного деления в столбик, делит <math>N</math> на <math>D</math>, помещая частное в <math>Q</math> и остаток в <math>R</math>. Все значения трактуются как целые числа без знака.

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

Пример

Возьмём <math>N = 1100_{2}</math> (<math>12_{10}</math>) и <math>D = 100_{2}</math> (<math>4_{10}</math>)

Шаг 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)

Конец
<math>Q = 11_{2}</math> (<math>3_{10}</math>) и <math>R = 0</math>.

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

Все методы медленного деления основываются на стандартном рекуррентном отношенииШаблон:Sfn

<math>R_{j+1} = B \times R_j - q_{n-(j+1)}\times D ,</math>

где:

<math>R_j</math> является j-м частичным остатком деления
B − основание счисления (равно обычно 2 в компьютерах и калькуляторах)
<math>q_{n-(j+1)}</math> является цифрой частного в позиции <math>n-(j+1)</math>, где позиции цифр пронумерованы от менее значащих цифр (0) к более значащим (<math>n-1</math>)
<math>n</math> − число знаков в частном
<math>D</math> − делитель

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

Восстанавливающее деление работает с дробными числами числами с плавающей запятой и зависит от предположения <math>0 < D < N</math>.

Цифры частного <math>q</math> формируются из набора <math>\{0, 1\}</math>.

Основной восстанавливающий алгоритм для двоичного (по основанию 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 частного

Вариант алгоритма, не осуществляющий явно <math>2R</math>, сохраняет его, а потому <math>D</math> не нужно добавлять обратно в случае <math>R < 0</math>.

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

Невосстанавливающее деление использует набор цифр <math>\{-1, 1\}</math> для цифр частного вместо <math>\{0, 1\}</math>. Алгоритм более сложен, но имеет преимущество, когда реализуется в микросхемах, что имеется всего одно принятие решения и одно сложение/вычитание на бит частного. Нет шага восстановления после вычитания, что может сократить число операций вдвое, и позволяет выполнить алгоритм быстрееШаблон:R. Алгоритм невосстанавливающего деления для двоичных (по основанию 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. Этот вид нужно преобразовывать в двоичную форму. Пример:

Преобразование частного к цифрам <math>\{0, 1\}</math>:
Старт:	<math>Q = 111\bar{1}1\bar{1}1\bar{1}</math>
1. Образуем положительный член:	<math>P = 11101010\,</math>
2. Образуем отрицательный член:	<math>M = 00010101\,</math>
3. Вычитаем: <math>P - M</math>:	<math>Q = 11010101\,</math>
Отрицательный член представлен в бинарном обратном коде, не в дополнительном коде

Если −1 знаки <math>Q</math> запомнены как нули (0), как в обычном представлении, то <math>P</math> является <math>Q</math> и вычисление <math>M</math> тривиально: осуществляет побитное дополнение (бит заменяется на дополнение бита) исходного <math>Q</math>.

Q := Q − bit.bnot(Q)      -- Если цифры −1 в Q представлены как нули.

Наконец, частные, вычисляемые этим алгоритмом, всегда нечётные, а остаток R находится в пределах <math>-D \leqslant R \leqslant D</math>. Например, <math>5/2 = 3R-1</math>. Для приведения к положительному остатку делаем один шаг восстановления после того, как <math>Q</math> приведена из нестандартного вида к стандартному:

if R < 0 then
  Q := Q − 1
  R := R + D  
end if

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

Шаблон:AnchorДеление SRT

Деление названо по первым буквам фамилий создателей (Sweeney, Robertson, Tocher). Деление SRT является популярным методом деления во многих микропроцессорах Шаблон:Sfn Шаблон:Sfn. Деление подобно делению без восстановления, но использует таблицу поиска на основе делимого и делителя для определения цифры частного.

Наиболее существенная разница в том, что используется избыточное представление для частного. Например, если реализуется деление SRT по основанию 4, каждая цифра частного выбирается из пяти возможностей: <math>\{-2, -1, 0, +1, +2\}</math>. Ввиду этого выбор цифры частного не обязательно должен быть точным. Позднее цифры частного можно откорректировать. Например, пары цифр <math>{0, +2}</math> и <math>{1, -2}</math> эквивалентны, поскольку <math>0{\times}4+2 = 1{\times}4-2</math>. Это допустимое отклонение позволяет выбирать цифры частного, исходя только из нескольких наиболее значащих бит делимого и делителя, вместо вычитания по полной длине. Это упрощение, в свою очередь, позволяет применять основание для чисел, большее 2.

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

Печально известный баг плавающего деления в процессорах Шаблон:Нп5 был вызван неправильно закодированной таблицей поиска. Пять из 1066 ячеек таблицы были ошибочно опущеныШаблон:R Шаблон:Sfn.

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

Деление Ньютона – Рапсона

Деление Ньютона – Рапсона использует метод Ньютона для нахождения обратного к <math>D</math> числа и умножает это обратное на <math>N</math>, чтобы найти результирующее частное <math>Q</math>.

Шаги деления Ньютона – Рапсона:

Вычисляем приближение <math>X_0</math> для обратного числа <math>1/D</math> делителя <math>D</math>.
Последовательно вычисляем более точные приближения <math>X_1,X_2,\ldots,X_S</math> обратного числа. Это место, где, собственно, и используется метод Ньютона – Рапсона.
Вычисляем частное путём умножения делимого на обратное к делителю: <math>Q = N X_S</math>.

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

что можно вычислить из <math>X_i</math>, используя только умножение и вычитание или два умножения-сложения.

С точки зрения вычислений выражения <math>X_{i+1} = X_i + X_i(1-DX_i)</math> и <math>X_{i+1} = X_i(2-DX_i)</math> не эквивалентны. Чтобы получить точность в 2n бит при использовании второго выражения, нужно вычислить произведение между <math>X_i</math> и <math>(2-DX_i)</math> с двойной точностью к заданной точности <math>X_i</math>(n бит). В отличие от этого произведение <math>X_i</math> и <math>(1-DX_i)</math> нужно вычислять только с точностью n бит, поскольку ведущие n бит (после двоичной точки) числа <math>(1-DX_i)</math> нулевые.

Если ошибка определяется как <math>\varepsilon_i = 1 - D X_i</math>, то

<math>\begin{align}

\varepsilon_{i+1} &= 1 - D X_{i+1} \\

              &= 1 - D (X_i(2-DX_i)) \\
              &= 1 - 2DX_i + D^2X_i^2 \\
              &= (1 - DX_i)^2 \\
              &= {\varepsilon_i}^2. \\

\end{align}</math> Эта ошибка в квадрате на каждом шаге итерации (так называемая квадратичная сходимость метода Ньютона – Рапсона) имеет эффект такой, что число верных знаков в результате, грубо говоря, удваивается для каждой итерации, свойство, которое становится крайне важным, когда встречающиеся числа имеют много знаков. Но это также означает, что начальная сходимость метода может оказаться сравнительно медленной, особенно если значение <math>X_0</math> выбрано плохо.

Для подзадачи выбора начальной оценки <math>X_0</math> удобно применить сдвиг делителя <math>D</math>, чтобы он оказался между <math>0{,}5 \leqslant D \leqslant 1</math>, с применением того же самого сдвига к делимому <math>N</math>, чтобы частное не изменилось. Тогда можно использовать линейную Аппроксимацию в виде

<math>X_0 = T_1 + T_2 D \approx \frac{1}{D} \,</math>

для инициализации метода Ньютона – Рапсона. Чтобы минимизировать максимальную абсолютную ошибку этого приближения на интервале <math>[0{,}5,1]</math>, следует использовать

Коэффициенты линейного приближения определяются следующим образом. Абсолютное значение ошибки равно <math>|\varepsilon_0| = |1 - D(T_1 + T_2 D)|</math>. Минимум максимального абсолютного значения ошибки определяется согласно Шаблон:Нп5, применённой к <math>F(D) = 1 - D(T_1 + T_2 D)</math>. Локальный минимум функции <math>F(D)</math> будет в точке, где <math>F'(D) = 0</math>, что имеет решение <math>D = -T_1/(2T_2)</math>. Функция в этом минимуме должна иметь значение с противоположным знаком по отношению к крайним точкам интервала, а именно, <math>F(1/2) = F(1) = -F(-T_1/(2T_2))</math>. Два равенства от двух неизвестных дают единственное решение <math>T_1 = 48/17</math> и <math>T_2 = -32/17</math>, а максимальная ошибка равна <math>F(1) = 1/17</math>. При использовании этого приближения абсолютное значение ошибки начального значения меньше, чем

<math>\vert \varepsilon_0 \vert \leqslant {1 \over 17} \approx 0{,}059 . \,</math>

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

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

<math>S = \left \lceil \log_2 \frac{P + 1}{\log_2 17} \right \rceil \,</math>

шагов для вычисления значения с точностью до <math>P \,</math> двоичных мест. Это эквивалентно 3 для IEEE чисел одинарной точности и 4 для чисел двойной точности и чисел расширенной двойной точности.

Псевдокод

Следующий псевдокод вычисляет частное от деления Шаблон:Var и Шаблон:Var с точностью до Шаблон:Var двоичных знаков:

Выражаем D как <math>M \times 2^e</math>, где <math>1 \leqslant M < 2</math> (стандартное представление  с плавающей запятой)
<math>D^\prime {\colon}= D / 2^{e+1}</math>   // приводим к значению между 0,5 и 1, что можно выполнить битовым сдвигом / вычитанием экспоненты
<math>N^\prime {\colon}= N / 2*{e+1}</math>
<math>X {\colon}= 48/17 - 32/17 \times D^\prime</math>   // заранее вычисленные константы с той же точностью, что и D
Шаблон:Nowrap   // может быть вычислено заранее для фиксированного P
    <math>X {\colon}= X + X \times (1 - D^\prime \times X)</math>
конец
возвратить <math>N^\prime \times X</math>

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

Варианты деления Ньютона – Рапсона

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

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

Это лучшее квадратичное приближение к <math>\frac{1}{D}</math> и оно даёт значение абсолютной ошибки не больше <math>1/99</math>. Параметры выбраны так, чтобы выбрать ошибку равной значению третьего порядка многочлена Чебышёва первого рода. Коэффициенты должны быть вычислены заранее и жёстко закодированы в методе.

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

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

<math>\left \lceil \log_3 \left(\frac{P + 1}{\log_2 99} \right) \right \rceil</math>

что равно числу раз возведения 99 в куб, чтобы получить <math>2^{P+1}</math>. Тогда

равно частному с точностью до <math>P</math> бит.

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

Шаблон:AnchorДеление Гольдшмидта

Деление ГольдшмидтаШаблон:Sfn (Robert Elliott Goldschmidt) использует итеративный процесс многократного умножения делимого и делителя на один и тот же множитель <math>F_i</math>, выбранный так, что делитель сходится к 1. Это приводит к тому, что делимое сходится к частному <math>Q</math>:

<math>Q = \frac{N}{D} \frac{F_1}{F_1} \frac{F_2}{F_2} \frac{F_\ldots}{F_\ldots}</math>

Шаги деления Гольдшмидта:

Генерируем приближение для множителя <math>F_i</math>.
Умножаем делимое и делитель на <math>F_i</math>.
Если делитель достаточно близок к 1, возвращаем делимое, в противном случае возвращаемся к шагу 1.

Предполагаем, что <math>N/D</math> масштабировано к значению <math>0 < D < 1</math>, каждый <math>F_i</math> основан на <math>D</math>:

Умножаем делимое и делитель на множитель и получаем:

После достаточного числа <math>k</math> итераций <math>Q=N_k</math>.

Метод Гольдшмидта используется в процессорах AMD Athlon и более поздних моделяхШаблон:Sfn Шаблон:Sfn. Он известен также как Anderson Earle Goldschmidt Powers (AEGP) алгоритм и реализован в различных процессорах IBMШаблон:Sfn Шаблон:Sfn. Хотя сходимость метода такая же, как у реализации Ньютона – Рапмона, одно из преимуществ метода Гольдшмидта в том, что умножения в числителе и знаменателе можно делать параллельноШаблон:Sfn.

Биномиальная теорема

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

<math>

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

</math>.

После <math>n</math> шагов <math>( x\in[0,\tfrac{1}{2}) )</math> знаменатель <math>1-x^{2^n}</math> можно округлить до <math>1</math> с относительной ошибкой

<math>

\varepsilon_n = \frac{Q' - N'}{Q'} = x^{2^n} </math>,

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

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

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

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

Деление на константу <math>D</math> эквивалентно умножению на её обратную величину. Поскольку знаменатель постоянен, постоянна и обратная величина <math>\frac{1}{D}</math>. Тогда можно вычислить значение <math>1/D</math> один раз и во время вычислений осуществляем умножение <math>N \times \frac{1}{D}</math> вместо деления <math>N/D</math>. В арифметике с плавающей запятой использование <math>\frac{1}{D}</math> вызывают небольшую проблему, связанную с оптимизацией кода компиляторамиШаблон:Efn, но в арифметике целых чисел остаток всегда будет равен нулю, при условии <math>|D| > 1</math>.

Нет необходимости использовать именно <math>1/D</math>, можно использовать любое значение <math>X/Y</math> которое сводится к <math>1/D</math>. Например, при делении на 3, можно использовать дроби <math>1/3</math>, <math>2/6</math>, <math>3/9</math> или <math>194/582</math>. Следовательно, когда <math>Y</math> является степенью двойки, шаг деления можно свести к быстрому правому сдвигу. Как эффект, вычисление <math>N/D</math> как <math>\frac{N \times X}{Y}</math> заменяет деление на умножение и сдвиг. Заметим, что именно такой порядок действий здесь существенен, поскольку <math>N \times \frac{X}{Y}</math> даст в результате нуль.

Однако, если <math>D</math> уже является степенью двойки, нет <math>X</math> и <math>Y</math>, удовлетворяющих условиям выше. К счастью, <math>\frac{N \times X}{Y}</math> даёт в точности тот же результат в арифметике целых чисел, что и <math>N/D</math>, даже если <math>X/Y</math> не в точности равно <math>1/D</math>, но «достаточно близко», так что ошибка, вносимая при аппроксимации находится в битах, которые уйдут после операции сдвигаШаблон:Sfn Шаблон:Sfn Шаблон:R Шаблон:Efn

В качестве конкретного примера арифметики с фиксированной запятой, для 32-битных беззнаковых целых, деление на 3 может быть заменено на умножение на <math>\tfrac{2863311531}{2^{33}}</math>, то есть умножением на 2863311531 (шестнадцатеричное 0xAAAAAAAB) с последующим сдвигом на 33 бита вправо. Значение 2863311531 вычислено как <math>\tfrac{2^{33}}{3}</math>, затем округлено. Аналогично деление на 10 может быть выражено как умножение на 3435973837 (0xCCCCCCCD) с последующим делением на <math>2^{35}</math> (или сдвигом вправо на 35 бит)Шаблон:Sfn. OEIS даёт последовательность констант для умножения как Шаблон:OEIS2C и для правого сдвига как Шаблон:OEIS2C.

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

<math>\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</math> где <math>b=\left\lfloor\frac{Na}{2^x}\right\rfloor</math>

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

См. также

Примечания

Шаблон:Комментарии Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Литература для дальнейшего чтения

Шаблон:Cite web

Шаблон:Теоретико-числовые алгоритмы

Шаблон:Rq

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.