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

А алгоритм деления является алгоритм который, учитывая два целых числа 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 больше -1 / X_ {i} ^ {2}} = X_ {i} + X_ {i} (1-DX_ {i}) = X_ {i} (2-DX_ {i}),}$

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

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

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

${ displaystyle { begin {align} 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}. конец {выровнено}}}$

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

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

${ Displaystyle X_ {0} = T_ {1} + T_ {2} D приблизительно { 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 более 17} приблизительно 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}} приблизительно 1} }}$.

После ${ displaystyle n}$ шаги ${ Displaystyle (х в [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 более 2}}$, обеспечивая минимальную точность ${ Displaystyle 2 ^ {п}}$ двоичные цифры.

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

Методы, разработанные для аппаратной реализации, обычно не масштабируются до целых чисел с тысячами или миллионами десятичных цифр; это часто встречается, например, в модульный сокращение криптография. Для этих больших целых чисел более эффективные алгоритмы деления преобразуют задачу, чтобы использовать небольшое количество умножений, которое затем может быть выполнено с использованием асимптотически эффективного алгоритм умножения такой как Алгоритм Карацубы, Умножение Тоома – Кука или Алгоритм Шёнхаге – Штрассена. В результате вычислительная сложность деления имеет тот же порядок (с точностью до мультипликативной константы), что и умножение. Примеры включают сокращение до умножения на Метод Ньютона так как описано выше,^[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]

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

Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Сентябрь 2012 г.)

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

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

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

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

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

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