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

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

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

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

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

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

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

это вход, а

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

это выход.

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

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

пока N ≥ D делать  N := N − Dконецвернуть N

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

функция разделять(N, D)  если D = 0 тогда ошибка(Деление на ноль) конец  если D < 0 тогда (Q, р) := разделять(N, −D); вернуть (−Q, р) конец  если N < 0 тогда    (Q,р) := разделять(−N, D)    если р = 0 тогда вернуть (−Q, 0)    еще вернуть (−Q − 1, D − р) конец  конец  - В этот момент N ≥ 0 и D> 0  вернуть div_unsigned(N, D)конец  функция div_unsigned(N, D)  Q := 0; р := N  пока р ≥ D делать    Q := Q + 1    р := р − D  конец  вернуть (Q, р)конец

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

Длинное деление

Основная статья: Деление в длину § Алгоритм для произвольной базы

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

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

Целочисленное деление (без знака) с остатком

Основная статья: Длинное деление § Двоичное деление

Смотрите также: Двоичное число § Деление

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

если D = 0 тогда ошибка(DivisionByZeroException) конецQ := 0                  - Инициализировать частное и остаток до нуляр := 0                     за я := п − 1 .. 0 делать  - Где n - количество бит в N  р := р << 1           - Сдвиг влево R на 1 бит  р(0) := N(я)          - Установить младший бит R равным i-му биту числителя  если р ≥ D тогда    р := р − 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

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

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

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

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

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

куда:

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

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

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

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

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

р := ND := D << п            - R и D должны вдвое превышать ширину слова N и Qза я := п − 1 .. 0 делать  - Например 31..0 для 32 бит  р := 2 * р − D          - Пробное вычитание из сдвинутого значения (умножение на 2 - это сдвиг в двоичном представлении)  если р ≥ 0 тогда    q(я) := 1          - бит результата 1  еще    q(я) := 0          - Бит результата 0    р := р + D         - Новый частичный остаток (восстанавливается) смещённое значение  конецконец- Где: N = числитель, D = знаменатель, n = # бит, R = частичный остаток, q (i) = бит #i частного

Вышеупомянутый восстанавливающий алгоритм деления может избежать этапа восстановления, сохранив смещенное значение 2.р перед вычитанием в дополнительном регистре Т (т.е. Т = р << 1) и копировальный аппарат Т к р когда результат вычитания 2р − D отрицательный.

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

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

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

р := ND := D << п            - R и D должны вдвое превышать ширину слова N и Qза я = п − 1 .. 0 делать  - например 31..0 для 32 бит  если р >= 0 тогда    q[я] := +1    р := 2 * р − D  еще    q[я] := −1    р := 2 * р + D  конец есликонец - Примечание: N = числитель, D = знаменатель, n = # битов, R = частичный остаток, q (i) = бит #i частного.

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

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

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

Q := Q − кусочек.bnot(Q)      * Подходящее если −1 Цифры в Q находятся Представлено так как нули так как является общий.

Наконец, частные, вычисленные этим алгоритмом, всегда нечетные, а остаток в R находится в диапазоне -D ≤ R после Q преобразуется из нестандартной формы в стандартную:

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

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

Отделение СТО

Названный в честь своих создателей (Суини, Робертсон и Точер), разделение СТО является популярным методом разделения во многих странах. микропроцессор реализации.^[4][5] Разделение SRT аналогично разделению без восстановления, но в нем используется Справочная таблица на основе делимого и делителя для определения каждой частной цифры.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Псевдокод

Следующее вычисляет частное от N и D с точностью до п двоичные места:

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

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

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

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

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

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

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

${\displaystyle E:=1-D\cdot X}$

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

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

В Y·E срок новый.

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

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

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

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

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

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

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

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

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

Шаги для подразделения Goldschmidt:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Однако если D сам по себе является степенью двойки, нет Икс и Y который удовлетворяет указанным выше условиям. К счастью, (N·Икс)/Y дает точно такой же результат, как N/D в целочисленной арифметике, даже если (Икс/Y) не совсем равно 1 /D, но «достаточно близко», чтобы ошибка, вносимая приближением, была в битах, которые отбрасываются операцией сдвига.^[16][17][18]

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

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

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

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

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

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

Смотрите также

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

Рекомендации

1. "Полное руководство по высшей математике по делению в столбик и его вариантам - для целых чисел". Математическое хранилище. 2019-02-24. Получено 2019-06-24.
2. Моррис, Джеймс Э .; Иневски, Кшиштоф (22.11.2017). Справочник по применению наноэлектронных устройств. CRC Press. ISBN  978-1-351-83197-0.
3. Флинн. «Stanford EE486 (Advanced Computer Arithmetic Division) - раздаточный материал по главе 5 (подразделение)» (PDF). Стэндфордский Университет.
4. Харрис, Дэвид Л .; Оберман, Стюарт Ф .; Горовиц, Марк А. (9 сентября 1998 г.). Подразделение SRT: архитектуры, модели и реализации (PDF) (Технический отчет). Стэндфордский Университет.
5. Макканн, Марк; Пиппенгер, Николас (2005). «Алгоритмы разделения СТО как динамические системы». SIAM Журнал по вычислениям. 34 (6): 1279–1301. CiteSeerX  10.1.1.72.6993. Дои:10.1137 / S009753970444106X.
6. «Статистический анализ дефекта с плавающей точкой». Корпорация Intel. 1994 г.. Получено 22 октября 2013.
7. Оберман, Стюарт Ф .; Флинн, Майкл Дж. (Июль 1995 г.). Анализ алгоритмов и реализаций деления (PDF) (Технический отчет). Стэндфордский Университет. CSL-TR-95-675.
8. Гольдшмидт, Роберт Э. (1964). Применения деления по сходимости (PDF) (Тезис). M.Sc. диссертация. M.I.T. OCLC  34136725.
9. https://web.archive.org/web/20180718114413/https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5392026
10. Оберман, Стюарт Ф. (1999). «Алгоритмы деления с плавающей запятой и извлечения квадратного корня и их реализация в микропроцессоре AMD-K7» (PDF). Материалы симпозиума IEEE по компьютерной арифметике: 106–115. Дои:10.1109 / ARITH.1999.762835. S2CID  12793819.
11. Содерквист, Питер; Лизер, Мириам (июль – август 1997 г.). «Деление и квадратный корень: выбор правильной реализации». IEEE Micro. 17 (4): 56–66. Дои:10.1109/40.612224.
12. С. Ф. Андерсон, Дж. Г. Эрл, Р. Э. Гольдшмидт, Д. М. Пауэрс. IBM 360/370 model 91: исполнительный модуль с плавающей запятой, Журнал исследований и разработок IBM, Январь 1997 г.
13. Гай Эвен, Питер-М. Зайдель, Уоррен Э. Фергюсон. Параметрический анализ ошибок алгоритма деления Гольдшмидта. 2004, [1]
14. Хассельстрём, Карл (2003). Быстрое деление больших целых чисел: сравнение алгоритмов (PDF) (Докторская диссертация по информатике). Королевский технологический институт. Архивировано из оригинал (PDF) 8 июля 2017 г.. Получено 2017-07-08.
15. Барретт, Пол (1987). «Реализация алгоритма шифрования открытого ключа Ривеста Шамира и Адлемана на стандартном цифровом сигнальном процессоре». Труды по достижениям в криптологии --- CRYPTO '86. Лондон, Великобритания: Springer-Verlag. С. 311–323. ISBN  0-387-18047-8.
16. Гранлунд, Торбьёрн; Монтгомери, Питер Л. (июнь 1994 г.). «Деление на инвариантные целые числа с использованием умножения» (PDF). Уведомления SIGPLAN. 29 (6): 61–72. CiteSeerX  10.1.1.1.2556. Дои:10.1145/773473.178249.
17. Мёллер, Нильс; Гранлунд, Торбьорн (февраль 2011 г.). «Улучшенное деление на инвариантные целые числа» (PDF). Транзакции IEEE на компьютерах. 60 (2): 165–175. Дои:10.1109 / TC.2010.143. S2CID  13347152.
18. смешная_рыба.«Труд разделения (Эпизод III): Более быстрое беззнаковое разделение константами».2011.
19. LaBudde, Robert A .; Головченко Николай; Ньютон, Джеймс; и Паркер, Дэвид; Massmind: "Бинарное деление на константу"
20. Гласные, Р. А. (1992). «Деление на 10». Австралийский компьютерный журнал. 24 (3): 81–85.

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

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