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

Алгоритмы вычисления частного и остатка от целочисленного деления

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

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

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

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

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

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

• Q = Частное
• R = Остаток

является выходом.

• 1 Деление повторным вычитанием
• 2 Длинное деление
  • 2.1 Целочисленное деление (без знака) с остатком
    • 2.1.1 Пример
• 3 Медленные методы деления
  • 3.1 Восстановление деления
  • 3.2 Невосстанавливающееся деление
  • 3.3 Разделение SRT
• 4 Методы быстрого деления
  • 4.1 Деление Ньютона – Рафсона
    • 4.1.1 Псевдокод
    • 4.1.2 Вариант деления Ньютона – Рафсона
  • 4.2 Деление Гольдшмидта
    • 4.2.1 Биномиальная теорема
• 5 Методы больших целых
• 6 Деление на константу
• 7 Ошибка округления
• 8 См. Также
• 9 Ссылки
• 10 Дополнительная литература
• 11 Внешние ссылки

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

пока N ≥ D do N: = N - D end return N

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

функция деления (N, D), если D = 0, то ошибка (DivisionByZero) end, если 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 вернуть div_unsigned (N, D) конец функции 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. В следующем коде все значения обрабатываются как целые числа без знака.

если D = 0, то ошибка (DivisionByZeroException) end Q: = 0 - инициализировать частное и остаток до нуля R: = 0 для i: = n - 1.. 0 do - где n - количество битов в NR : = 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 2 (12 10) и D = 100 2(410)

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

Шаг 2: Установите i = 2. Шаг 3: R = 010. Шаг 4: R = 011. Шаг 5: R

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

end. Q = 11 2(310) и R = 0.

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

$R\; j\; +\; 1\; =\; B\; \times \; R\; j\; -\; qn\; -\; (j\; +\; 1)\; \times \; D\; \{\backslash \; displaystyle\; R\_\; \{j\; +\; 1\}\; =\; B\; \backslash \; times\; R\_\; \{j\}\; -q\_\; \{n-\; (j\; +\; 1)\}\; \backslash \; times\; D\; \backslash ,\}$,

где:

• Rj- j-й частичный остаток от деления
• B - система счисления (основание, обычно 2 внутри компьютеров и калькуляторов)
• qn - (j + 1) - цифра частного в позиции n− (j + 1), где позиции цифр пронумерованы от наименее значимого 0 до наиболее значимого n − 1
• n - количество цифр в частном
• D - делитель

Восстановление деления

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

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

Базовый алгоритм для двоичного (основание 2) восстанавливающего деления:

R: = ND: = 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 перед вычитание в дополнительном регистре T (т. е. T = R << 1) and copying register T to R when the result of the subtraction 2R − D is negative.

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

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

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

R: = ND: = 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, затем q [i] : = +1 R: = 2 * R - D иначе q [i]: = −1 R: = 2 * R + D конец, если конец - Примечание: N = числитель, D = знаменатель, n = # бит, R = Частичный остаток, q (i) = бит #i частного.

Следуя этому алгоритму, частное имеет нестандартную форму, состоящую из цифр -1 и +1. Эта форма должна быть преобразована в двоичную, чтобы получить окончательное частное. Пример:

Преобразование следующего частного в набор цифр {0,1}:
Начало:	$Q\; =\; 111\; 1\; ¯\; 1\; 1\; ¯\; 1\; 1\; ¯\; \{\backslash \; displaystyle\; Q\; =\; 111\; \{\backslash \; bar\; \{1\}\; \}\; 1\; \{\backslash \; bar\; \{1\}\}\; 1\; \{\backslash \; bar\; \{1\}\}\}$
1. Сформируйте положительный член:	$P\; =\; 11101010\; \{\backslash \; displaystyle\; P\; =\; 11101010\; \backslash ,\}$
2. Замаскируйте отрицательный член *:	$M\; =\; 00010101\; \{\backslash \; displaystyle\; M\; =\; 00010101\; \backslash ,\}$
3. Вычтите: $P\; -\; M\; \{\backslash \; displaystyle\; PM\}$:	$Q\; =\; 11010101\; \{\backslash \; displaystyle\; Q\; =\; 11010101\; \backslash ,\}$
*. (Знаковое двоичное представление с дополнением до единицы без Дополнение до двух )

Если -1 цифра в $Q\; \{\backslash \; displaystyle\; Q\}$сохранена как обычные нули (0), то $P\; \{\backslash \; displaystyle\; P\}$is$Q\; \{\backslash \; displaystyle\; Q\}$и вычисление $M\; \{\backslash \; displaystyle\; M\}$тривиально: выполнить дополнение до единицы (побитовое дополнение) на исходном $Q\; \{\; \backslash \; displaystyle\; Q\}$.

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

Наконец, частные, вычисленные этим алгоритмом, всегда нечетные, а остаток в R находится в диапазоне -D ≤ R < D. For example, 5 / 2 = 3 R −1. To convert to a positive remainder, do a single restoring step after Q is converted from non-standard form to standard form:

, если R < 0 then Q := Q − 1 R := R + D -- Needed only if the Remainder is of interest. end if

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

SRT-разделение

Названо в честь его создателей (Суини, Ro Bertson и Tocher), разделение SRT является популярным методом разделения во многих реализациях микропроцессора. Разделение SRT аналогично разделению без восстановления, но оно использует таблицу поиска на основе делимого и делителя для определения каждой цифры частного.

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

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

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

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

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

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

1. Вычислить оценку $X\; 0\; \{\backslash \; displaystyle\; X\_\; \{0\}\}$для обратного $1\; /\; D\; \{\backslash \; displaystyle\; 1\; /\; D\}$делителя $D\; \{\backslash \; displaystyle\; D\}$.
2. Последовательное вычисление более точных оценок $X\; 1,\; X\; 2,\dots ,\; XS\; \{\backslash \; displaystyle\; X\_\; \{1\},\; X\_\; \{2\},\; \backslash \; ldots,\; X\_\; \{S\}\}$обратного. Именно здесь применяется метод Ньютона – Рафсона как таковой.
3. Вычислить частное, умножив делимое на обратную величину делителя: $Q\; =\; NXS\; \{\backslash \; displaystyle\; Q\; =\; NX\_\; \{S\}\}$.

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

$X\; i\; +\; 1\; =\; X\; i\; -\; f\; (X\; i)\; f\; \prime \; (X\; i)\; =\; X\; i\; -\; 1\; /\; X\; i\; -\; D\; -\; 1\; /\; X\; i\; 2\; =\; X\; i\; +\; X\; i\; (1\; -\; DX\; я)\; знак\; равно\; Икс\; я\; (2\; -\; DX\; я),\; \{\backslash \; Displaystyle\; X\_\; \{я\; +\; 1\}\; =\; X\_\; \{я\}\; -\; \{е\; (X\_\; \{я\})\; \backslash \; над\; f\; \text{'}(X\_\; \{i\})\}\; =\; X\_\; \{я\; \}\; -\; \{1\; /\; X\_\; \{i\}\; -D\; \backslash \; over\; -1\; /\; X\_\; \{i\}\; ^\; \{2\}\}\; =\; X\_\; \{i\}\; +\; X\_\; \{i\}\; (1-DX\_\; \{i\})\; =\; X\_\; \{i\}\; (2\; -DX\_\; \{i\}),\}$

который может быть вычислен из $X\; i\; \{\backslash \; displaystyle\; X\_\; \{i\}\}$, используя только умножение и вычитание, или используя два объединенного умножения– добавляет.

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

Если ошибка определяется как $\epsilon \; i\; =\; 1\; -\; DX\; i\; \{\backslash \; displaystyle\; \backslash \; varepsilon\; \_\; \{i\}\; =\; 1-DX\_\; \{i\}\}$, то:

$\epsilon \; i\; +\; 1\; =\; 1\; -\; DX\; i\; +\; 1\; =\; 1\; -\; D\; (X\; i\; (2\; -\; DX\; i))\; =\; 1-2\; DX\; i\; +\; D\; 2\; X\; i\; 2\; =\; (1\; -\; DX\; i)\; 2\; =\; \epsilon \; i\; 2.\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; \backslash \; varepsilon\; \_\; \{i\; +\; 1\}\; =\; 1-DX\_\; \{i\; +\; 1\}\; \backslash \backslash \; =\; 1-D\; (X\_\; \{i\}\; (2-DX\_\; \{i\}))\; \backslash \backslash \; =\; 1-2DX\_\; \{i\}\; +\; D\; ^\; \{2\}\; X\_\; \{i\}\; ^\; \{2\}\; \backslash \backslash \; =\; (1-DX\_\; \{i\})\; ^\; \{2\}\; \backslash \backslash \; =\; \{\backslash \; varepsilon\; \_\; \{i\}\}\; ^\; \{2\}.\; \backslash \backslash \backslash \; end\; \{align\}\}\}$

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

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

$X\; 0\; =\; T\; 1\; +\; T\; 2\; D\; \approx \; 1\; D\; \{\backslash \; displaystyle\; X\_\; \{0\}\; =\; T\_\; \{1\}\; +\; T\_\; \{2\}\; D\; \backslash \; приблизительно\; \{\backslash \; frac\; \{1\}\; \{D\}\}\; \backslash ,\}$

для инициализации Ньютона – Рафсона. Чтобы минимизировать максимум абсолютного значения ошибки этого приближения на интервале $[0,5,\; 1]\; \{\backslash \; displaystyle\; [0,5,1]\}$, следует использовать

$X\; 0\; =\; 48\; 17\; -\; 32\; 17\; Д.\; \{\backslash \; displaystyle\; X\_\; \{0\}\; =\; \{48\; \backslash \; over\; 17\}\; -\; \{32\; \backslash \; over\; 17\}\; D.\; \backslash ,\}$

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

$|\; \epsilon \; 0\; |\; \le \; 1\; 17\; \approx \; 0,059.\; \{\backslash \; displaystyle\; \backslash \; vert\; \backslash \; varepsilon\; \_\; \{0\}\; \backslash \; vert\; \backslash \; leq\; \{1\; \backslash \; over\; 17\}\; \backslash \; приблизительно\; 0,059.\; \backslash ,\}$

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

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

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

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

Псевдокод

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

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

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

Вариант деления Ньютона-Рафсона

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

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

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

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

$E:\; =\; 1\; -\; D\; \cdot \; Икс\; \{\backslash \; displaystyle\; E:\; =\; 1-D\; \backslash \; cdot\; X\}$

$Y:\; =\; X\; \cdot \; E\; \{\backslash \; displaystyle\; Y:\; =\; X\; \backslash \; cdot\; E\}$

$X:\; =\; X\; +\; Y\; +\; Y\; \cdot \; E.\; \{\backslash \; displaystyle\; X:\; =\; X\; +\; Y\; +\; Y\; \backslash \; cdot\; E.\}$

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

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

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

, которое является числом количество умноженных на 99 необходимо кубов, чтобы получить 2. Тогда

$Q:\; =\; N\; \cdot \; X\; \{\backslash \; displaystyle\; Q:\; =\; N\; \backslash \; cdot\; X\}$

является частным к P битам.

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

Деление Гольдшмидта

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

$Q\; =\; NDF\; 1\; F\; 1\; F\; 2\; F\; 2\; F\dots \; F\dots .\; \{\backslash \; displaystyle\; Q\; =\; \{\backslash \; frac\; \{N\}\; \{D\}\}\; \{\backslash \; frac\; \{F\_\; \{1\}\}\; \{F\_\; \{1\}\}\}\; \{\backslash \; frac\; \{F\_\; \{2\}\}\; \{F\_\; \{2\}\}\}\; \{\backslash \; frac\; \{F\; \_\; \{\backslash \; ldots\}\}\; \{F\; \_\; \{\backslash \; ldots\}\}\}.\}$

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

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

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

$F\; i\; +\; 1\; =\; 2\; -\; D\; я.\; \{\backslash \; displaystyle\; F\_\; \{i\; +\; 1\}\; =\; 2-D\_\; \{i\}.\}$

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

$N\; i\; +\; 1\; D\; i\; +\; 1\; =\; N\; i\; D\; i\; F\; i\; +\; 1\; Ф\; я\; +\; 1.\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{N\_\; \{i\; +\; 1\}\}\; \{D\_\; \{i\; +\; 1\}\}\}\; =\; \{\backslash \; frac\; \{N\_\; \{i\}\}\; \{D\_\; \{i\}\}\}\; \{\backslash \; frac\; \{F\_\; \{i\; +\; 1\}\; \}\; \{F\_\; \{i\; +\; 1\}\}\}.\}$

После достаточного числа k итераций $Q\; =\; N\; k\; \{\backslash \; displaystyle\; Q\; =\; N\_\; \{k\}\}$.

Метод Гольдшмидта используется в AMD процессоры Athlon и более поздние модели. Он также известен как алгоритм Андерсона Эрла Голдшмидта (AEGP) и реализуется различными процессорами IBM.

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

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

$N\; 1\; -\; x\; =\; N\; \cdot \; (1\; +\; x)\; 1\; -\; x\; 2\; =\; N\; \cdot \; (1\; +\; x)\; \cdot \; (1\; +\; x\; 2)\; 1\; -\; x\; 4\; =\; \cdots \; =\; Q\; \prime \; =\; N\; \prime \; =\; N\; \cdot \; (1\; +\; x)\; \cdot \; (1\; +\; x\; 2)\; \cdot \; \cdot \; \cdot \; (1\; +\; x\; 2\; (n\; -\; 1))\; D\; \prime \; =\; 1\; -\; x\; 2\; n\; \approx \; 1\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{N\}\; \{1-x\}\}\; =\; \{\backslash \; frac\; \{N\; \backslash \; cdot\; (1\; +\; x)\}\; \{1-x\; ^\; \{2\}\}\}\; =\; \{\backslash \; frac\; \{N\; \backslash \; cdot\; (1\; +\; x)\; \backslash \; cdot\; (1\; +\; x\; ^\; \{2\})\}\; \{1-x\; ^\; \{4\}\}\}\; =\; \backslash \; cdots\; =\; Q\; \text{'}=\; \{\backslash \; frac\; \{N\text{'}\; =\; N\; \backslash \; cdot\; (1\; +\; x)\; \backslash \; cdot\; (1\; +\; x\; ^\; \{2\})\; \backslash \; cdot\; \backslash \; cdot\; \backslash \; cdot\; (1\; +\; x\; ^\; \{2\; ^\; \{(n-1)\}\})\}\; \{D\; \text{'}=\; 1-x\; ^\; \{\; 2\; ^\; \{n\}\}\; \backslash \; приблизительно\; 1\}\}\}$.

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

$\epsilon \; n\; =\; Q\; \prime \; -\; N\; \prime \; Q\; \prime \; =\; x\; 2\; n\; \{\; \backslash \; Displaystyle\; \backslash \; varepsilon\; \_\; \{n\}\; =\; \{\backslash \; frac\; \{Q\text{'}-N\; \text{'}\}\; \{Q\text{'}\}\}\; =\; x\; ^\; \{2\; ^\; \{n\}\}\}$

, максимальное значение $2–2\; n\; \{\backslash \; displaystyle\; 2\; ^\; \{-\; 2\; ^\; \{n\}\}\}$когда $x\; =\; 1\; 2\; \{\backslash \; displaystyle\; x\; =\; \{1\; \backslash \; over\; 2\}\}$, обеспечивая минимальную точность $2\; n\; \{\backslash \; displaystyle\; 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, но «достаточно близко», чтобы ошибка, вносимая приближением, была в битах, которые отбрасываются операцией сдвига.

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

Подобным образом деление на 10 может быть выражено как умножение на 3435973837 (0xCCCCCCCD) с последующим делением на 2 (или сдвиг на 35 битов вправо).

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

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

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

• Уоррен-младший, Генри С. (2013). Hacker's Delight (2-е изд.). Эддисон Уэсли - Pearson Education, Inc. ISBN 978-0-321-84268-8.
• Савард, Джон Дж. Дж. (2018) [ 2006]. «Продвинутые арифметические методы». квадиблок. Архивировано из оригинала 2018-07-03. Проверено 16 июля 2018 г.

• Симулятор компьютерных арифметических алгоритмов JavaScript - содержит симуляторы для многих различных алгоритмов деления
• Дорас, Кори (19 октября 2011 г.). «Труд разделения (Эпизод III): Более быстрое беззнаковое разделение константами» (PDF). ridiculous_fish. (Расширяет деление на константы.)
• Целочисленное деление
• Алгоритмы деления и аппаратные реализации
• Программное деление и квадратный корень с использованием алгоритмов Гольдшмидта