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

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

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

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

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

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

это вход, а

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

это выход.

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

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

в то время как  N  ≥  D  do  N  : =  N  -  D end return  N

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

функция  div ( N ,  D ),  если  D  =  0,  то  ошибка ( DivisionByZero )  end,  если  D  <  0,  то  ( Q ,  R )  : =  div ( N ,  - D );  return  ( - Q ,  R )  end,  если  N  <  0,  то  ( Q , R )  : =  разделить( - N ,  D )  если  R  =  0,  то  верните  ( - Q ,  0 )  иначе  верните  ( - Q  -  1 ,  D  -  R )  конец  конец  - В этот момент N ≥ 0 и D> 0  вернут  div_unsigned ( N ,  D ) конечная  функция  div_unsigned ( N ,  D )  Q  : =  0 ;  р : =  N,  а  R  ≥  D  сделать  Q  : =  Q  +  1  R  : =  R  -  D  конец  возврат  ( Q ,  R ) конец

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

Длинное деление [ править ]

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

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

Целочисленное деление (без знака) с остатком [ править ]

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

если  D  =  0,  то  ошибка ( DivisionByZeroException )  end Q  : =  0  - Инициализировать частное и остаток до нуля R  : =  0  для  i  : =  n  -  1  ..  0  do  - Где n - количество битов в N  R  : =  R  <<  1  - сдвиг влево R на 1 бит  R ( 0 )  : =  N ( i ) - Установите младший бит R равным биту i числителя,  если  R  ≥  D,  то  R  : =  R  -  D  Q ( i )  : =  1  end end

Пример [ править ]

Если взять N = 1100 ₂ (12 ₁₀ ) и D = 100 ₂ (4 ₁₀ )

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

Шаг 2 : Установите i = 2
Шаг 3 : R = 010
Шаг 4 : R = 011
Шаг 5 : R <D, оператор пропущен

Шаг 2 : Установите i = 1
Шаг 3 : R = 0110
Шаг 4 : R = 0110
Шаг 5 : R> = D, оператор введен
Шаг 5b : R = 10 (R − D)
Шаг 5c : Q = 10 (установка Q ( i) к 1)

Шаг 2 : Установите i = 0
Шаг 3 : R = 100
Шаг 4 : R = 100
Шаг 5 : R> = D, оператор введен
Шаг 5b : R = 0 (R − D)
Шаг 5c : Q = 11 (установка Q ( i) к 1)

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

Медленные методы деления [ править ]

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

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

куда:

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

Восстановление разделения [ править ]

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

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

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

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

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

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

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

R  : =  N D  : =  D  <<  n  - R и D требуют удвоенной ширины слова N и Q для  i  =  n  -  1  ..  0  do  - например 31..0 для 32 бит,  если  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}:
Начинать:	${\ displaystyle Q = 111 {\ bar {1}} 1 {\ bar {1}} 1 {\ bar {1}}}$
1. Сформируйте положительный термин:	${\ Displaystyle P = 11101010 \,}$
2. Замаскируйте отрицательный термин *:	${\ Displaystyle M = 00010101 \,}$
3. Вычтите ::${\ displaystyle PM}$	${\ Displaystyle Q = 11010101 \,}$
*. (Знаковая двоичная запись с дополнением до единицы без дополнения до двух )

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

Q  : =  Q  -  бит . BNOT ( Q )  *  Подходит ,  если  - 1  Цифры  в  Q  являются  Представлял ,  как  нули ,  как  это  общее .

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

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

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

Отделение SRT [ править ]

Названный в честь его создателей (Суини, Робертсон и Точер), разделение SRT является популярным методом разделения во многих реализациях микропроцессоров . ^{[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}}$

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

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

${\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.\,}$

Коэффициенты линейной аппроксимации определяются следующим образом. Абсолютное значение ошибки составляет . Минимум максимального абсолютного значения ошибки определяется Чебышев equioscillation теоремы применяется к . Локальный минимум возникает тогда , когда есть решение . Функция в этом минимуме должна иметь знак, противоположный знаку функции в конечных точках, а именно . Два уравнения с двумя неизвестными имеют единственное решение и , а максимальная ошибка равна . При таком приближении абсолютное значение погрешности начального значения меньше${\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 \,}$

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

Псевдокод [ править ]

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

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

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

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

что является числом 99, которое необходимо возвести в куб, чтобы получить 2 ^{P +1} . потом

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

отношение к P битам.

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

Отделение Гольдшмидта [ править ]

Деление Гольдшмидта ^[8] (после Роберта Эллиотта Гольдшмидта ^[9] ) использует итерационный процесс многократного умножения делимого и делителя на общий множитель F _i , выбранный таким образом, чтобы делитель сходился к 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 _i .
2. Умножьте дивиденд и делитель на F _i .
3. Если делитель достаточно близок к 1, верните делимое, в противном случае перейдите к шагу 1.

Предполагая, что N / D было масштабировано так, что 0 <  D  <1, каждый F _i основан на 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 ); может использоваться любое значение ( 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 , но «достаточно близко», чтобы ошибка, вносимая приближением, была в битах, которые отбрасываются операцией сдвига. ^{[16] [17] [18]}

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

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

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

Ошибка округления [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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