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

Метод деления с остатком

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

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

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

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

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

это вход, и

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

это выход.

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

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

R  : =  N Q  : =  0 в то время как  R  ≥  D  do  R  : =  R  -  D  Q  : =  Q  +  1 конец возврата  ( Q , R )

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

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

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

Шаг 2 : Установить i=0
Шаг 3 : R=100
Шаг 4 : R=100
Шаг 5 : R>=D, введен оператор
Шаг 5b : R=0 (R-D)
Шаг 5c : Q=11 (установка Q( я) к 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  else  q ( i )  : =  0  -- Бит результата 0  R  : =  R  +  D  -- Новый частичный остаток (восстанавливается) сдвинутого значения  end end-- Где: N = числитель, D = знаменатель, n = #бит, R = частичный остаток, q(i) = бит #i частного

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

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

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

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

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

Если цифры -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 — популярный метод деления во многих реализациях микропроцессоров . ^{[5] [6]} Алгоритм назван в честь Д.В. Суини из IBM , Джеймса Э. Робертсона из Университета Иллинойса и К.Д. Точера из Имперского колледжа Лондона . Все они разработали алгоритм независимо друг от друга примерно в одно и то же время (опубликовано в феврале 1957 г., сентябре 1958 г. и январе 1958 г. соответственно). ^{[7] [8] [9]}

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

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

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

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

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

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

Ньютон-Рафсон использует метод Ньютона , чтобы найти обратную величину и умножить эту обратную величину на, чтобы найти окончательное частное . ${\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.\,}$

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

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

Гольдшмидтское подразделение

Деление Гольдшмидта ^{[12] (вслед за} _{Робертом} Эллиотом Гольдшмидтом) ^[13] использует итерационный процесс многократного умножения делимого и делителя на общий множитель Fi , выбранный так, чтобы делитель сходился к 1. Это заставляет делимое сходиться к искомое частное Q :

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

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

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 и более поздних моделях. ^{[14] [15]} Он также известен как алгоритм Андерсона Эрла Гольдшмидта Пауэрса (AEGP) и реализуется различными процессорами IBM. ^{[16] [17]} Хотя он сходится с той же скоростью, что и реализация Ньютона-Рафсона, одним из преимуществ метода Гольдшмидта является то, что умножения в числителе и знаменателе могут выполняться параллельно. ^[17]

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

Метод Гольдшмидта можно использовать с факторами, допускающими упрощения по биномиальной теореме . Предположим , что масштабирован в степени двойки так, что . Выбираем и . Это дает ${\displaystyle N/D}$ ${\displaystyle D\in \left({\tfrac {1}{2}},1\right]}$ ${\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}}}$$

.

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

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

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

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

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

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

Деление на константу D эквивалентно умножению на обратную величину . Поскольку знаменатель постоянен, то и его обратная величина (1/ D ) постоянна. Таким образом, можно вычислить значение (1/ D ) один раз во время компиляции, а во время выполнения выполнить умножение N ·(1/ D ), а не деление N/D . В арифметике с плавающей запятой использование (1/ D ) не представляет особых проблем, ^[a] но в целочисленной арифметике обратная величина всегда будет равна нулю (при условии | 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 , но «достаточно близко», чтобы ошибка, вносимая аппроксимацией, составляла в битах, которые отбрасываются в результате операции сдвига. ^{[21] [22] [23]} При сокращении Барретта для значения Y используются степени 2 , чтобы сделать деление на Y простым сдвигом вправо. ^[б]

В качестве конкретного примера арифметики с фиксированной запятой для 32-битных целых чисел без знака деление на 3 можно заменить умножением на2863311531/2 ³³, умножение на 2863311531 ( шестнадцатеричное 0xAAAAAAAB), за которым следует сдвиг вправо на 33 бита. Значение 2863311531 рассчитывается как2 ³³/3, затем округляем в большую сторону. Аналогично, деление на 10 можно выразить как умножение на 3435973837 (0xCCCCCCCD), за которым следует деление на 2 ³⁵ (или сдвиг правого бита на 35). ^{[25] : p230-234} OEIS предоставляет последовательности констант для умножения как A346495 и для сдвига вправо как A346496.

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

${\displaystyle \left\lfloor {\frac {N}{D}}\right\rfloor =\left\lfloor {\frac {\left\lfloor {\frac {N-b}{2}}\right\rfloor +b}{2^{k-x-1}}}\right\rfloor {\text{ where }}b=\left\lfloor {\frac {Na}{2^{x}}}\right\rfloor }$

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

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

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

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

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

Примечания

1. компиляторах все еще обычно скрывается за флагом «быстрой математики», поскольку она неточна.
2. Современные компиляторы обычно выполняют эту оптимизацию целочисленного умножения и сдвига; однако для константы, известной только во время выполнения, программа должна сама реализовать оптимизацию. ^[24]

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

1. Родехеффер, Томас Л. (26 августа 2008 г.). Software Integer Division (PDF) (Технический отчет). Microsoft Research, Кремниевая долина.
2. Моррис, Джеймс Э.; Иневский, Кшиштоф (22 ноября 2017 г.). Справочник по применению наноэлектронных устройств. ЦРК Пресс. ISBN 978-1-351-83197-0.
3. Шоу, Роберт Ф. (1950). «Арифметические операции в двоичном компьютере». Обзор научных инструментов . 21 (8): 690. Бибкод : 1950RScI...21..687S. дои : 10.1063/1.1745692. ISSN  0034-6748. Архивировано из оригинала 28 февраля 2022 г. Проверено 28 февраля 2022 г.
4. Флинн. «Stanford EE486 (Отдел продвинутой компьютерной арифметики) - Раздаточный материал главы 5 (Отдел)» (PDF) . Стэндфордский Университет . Архивировано (PDF) из оригинала 18 апреля 2022 г. Проверено 24 июня 2019 г.
5. Харрис, Дэвид Л.; Оберман, Стюарт Ф.; Горовиц, Марк А. (9 сентября 1998 г.). Отдел SRT: Архитектура, модели и реализации (PDF) (Технический отчет). Стэндфордский Университет. Архивировано (PDF) из оригинала 24 декабря 2016 года . Проверено 23 декабря 2016 г.
6. Макканн, Марк; Пиппенджер, Николас (2005). «Алгоритмы разделения СТО как динамические системы». SIAM Journal по вычислительной технике . 34 (6): 1279–1301. CiteSeerX 10.1.1.72.6993 . дои : 10.1137/S009753970444106X. Архивировано из оригинала 24 августа 2022 г. Проверено 24 августа 2022 г. 
7. Кок, Джон; Суини, Д.В. (11 февраля 1957 г.), Высокоскоростная арифметика в параллельном устройстве (Company Memo), IBM, стр. 20, заархивировано из оригинала 24 августа 2022 года , получено 24 августа 2022 года.{{citation}}: CS1 maint: location missing publisher (link)
8. Робертсон, Джеймс (1958-09-01). «Новый класс методов цифрового деления». IRE-транзакции на электронных компьютерах . IEEE. ЕС-7 (3): 218–222. дои : 10.1109/TEC.1958.5222579. hdl : 2027/uiuo.ark:/13960/t0gt7529c . Архивировано из оригинала 24 августа 2022 г. Проверено 24 августа 2022 г.
9. Точер, К.Д. (1 января 1958 г.). «Методы умножения и деления для автоматических двоичных компьютеров». Ежеквартальный журнал механики и прикладной математики . 11 (3): 364–384. дои : 10.1093/qjmam/11.3.364. Архивировано из оригинала 24 августа 2022 г. Проверено 24 августа 2022 г.
10. «Статистический анализ ошибок с плавающей запятой» . Корпорация Интел. 1994. Архивировано из оригинала 23 октября 2013 года . Проверено 22 октября 2013 г.
11. Оберман, Стюарт Ф.; Флинн, Майкл Дж. (июль 1995 г.). Анализ алгоритмов и реализаций разделения (PDF) (Технический отчет). Стэндфордский Университет. CSL-TR-95-675. Архивировано (PDF) из оригинала 17 мая 2017 г. Проверено 23 декабря 2016 г.
12. Гольдшмидт, Роберт Э. (1964). Применение деления по сходимости (PDF) (Диссертация). Магистр наук диссертация. MIT OCLC  34136725. Архивировано (PDF) из оригинала 10 декабря 2015 г. Проверено 15 сентября 2015 г.
13. «Авторы». Журнал исследований и разработок IBM . 11 : 125–127. 1967. дои : 10.1147/рд.111.0125. Архивировано из оригинала 18 июля 2018 года.
14. Оберман, Стюарт Ф. (1999). «Алгоритмы деления с плавающей запятой и квадратного корня и их реализация в микропроцессоре AMD-K7TM» (PDF) . Материалы 14-го симпозиума IEEE по компьютерной арифметике (кат. № 99CB36336) . стр. 106–115. дои : 10.1109/ARITH.1999.762835. ISBN 0-7695-0116-8. S2CID  12793819. Архивировано (PDF) из оригинала 29 ноября 2015 г. Проверено 15 сентября 2015 г.
15. Содерквист, Питер; Лизер, Мириам (июль – август 1997 г.). «Деление и квадратный корень: выбор правильной реализации». IEEE микро . 17 (4): 56–66. дои : 10.1109/40.612224.
16. С.Ф. Андерсон, Дж.Г. Эрл, Р.Е. Гольдшмидт, Д.М. Пауэрс. IBM 360/370 model 91: исполнительный блок с плавающей запятой , IBM Journal of Research and Development , январь 1997 г.
17. Гай, Эвен; Питер, Зидель; Фергюсон, Уоррен (1 февраля 2005 г.). «Параметрический анализ ошибок алгоритма деления Гольдшмидта». Журнал компьютерных и системных наук . 70 (1): 118–139. дои : 10.1016/j.jcss.2004.08.004 .
18. Хассельстрем, Карл (2003). Быстрое деление больших целых чисел: сравнение алгоритмов (PDF) (диссертация на степень магистра компьютерных наук). Королевский технологический институт. Архивировано из оригинала (PDF) 8 июля 2017 года . Проверено 8 июля 2017 г.
19. Иоахим Циглер, Кристоф Бурникель (1998), Отдел быстрой рекурсии, Институт Макса Планка по информатике, заархивировано из оригинала 26 апреля 2011 г. , получено 10 сентября 2021 г.{{citation}}: CS1 maint: location missing publisher (link)
20. Барретт, Пол (1987). «Реализация алгоритма шифрования с открытым ключом Ривеста Шамира и Адлемана на стандартном процессоре цифровых сигналов». Труды о достижениях в криптологии --- CRYPTO '86 . Лондон, Великобритания: Springer-Verlag. стр. 311–323. ISBN 0-387-18047-8.
21. Гранлунд, Торбьёрн; Монтгомери, Питер Л. (июнь 1994 г.). «Деление на инвариантные целые числа с использованием умножения» (PDF) . Уведомления SIGPLAN . 29 (6): 61–72. CiteSeerX 10.1.1.1.2556 . дои : 10.1145/773473.178249. Архивировано (PDF) из оригинала 6 июня 2019 г. Проверено 8 декабря 2015 г. 
22. Мёллер, Нильс; Гранлунд, Торбьорн (февраль 2011 г.). «Улучшенное деление инвариантными целыми числами» (PDF) . Транзакции IEEE на компьютерах . 60 (2): 165–175. дои : 10.1109/TC.2010.143. S2CID  13347152. Архивировано (PDF) из оригинала 22 декабря 2015 г. Проверено 8 декабря 2015 г.
23. смешная_рыба. «Труд разделения (Эпизод III): более быстрое деление без знака константами». Архивировано 8 января 2022 г. в Wayback Machine . 2011.
24. смешная_рыба. «libdivide, оптимизированное целочисленное деление». Архивировано из оригинала 23 ноября 2021 года . Проверено 6 июля 2021 г.
25. Уоррен-младший, Генри С. (2013). Хакерское наслаждение (2-е изд.). Аддисон Уэсли - ISBN Pearson Education, Inc.  978-0-321-84268-8.
26. ЛаБудд, Роберт А.; Головченко, Николай; Ньютон, Джеймс; и Паркер, Дэвид; Massmind: «Двоичное деление на константу». Архивировано 9 января 2022 г. на Wayback Machine.
27. Гласные, РА (1992). «Деление на 10». Австралийский компьютерный журнал . 24 (3): 81–85.

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

• Савард, Джон Дж. Г. (2018) [2006]. «Продвинутые арифметические методы». четырехблок . Архивировано из оригинала 3 июля 2018 г. Проверено 16 июля 2018 г.