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

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

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

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

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

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

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

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

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

это выход.

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

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

R  : =  N Q  : =  0 пока  R  ≥  D  сделать  R  : =  R  −  D  Q  : =  Q  +  1 конец вернуть  ( Q , R )

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

function  divide ( N ,  D )  if  D  =  0  then  error ( DivisionByZero )  end  if  D  <  0  then  ( Q ,  R )  : =  divided ( N ,  −D ) ; return ( −Q , R ) end if N < 0 then ( Q , R ) : = divided ( −N , D ) if R = 0 then return ( −Q , 0 ) else return ( −Q − 1 , D − R ) end end -- В этой точке N ≥ 0 и D > 0 return divide_unsigned ( N , D ) end function divide_unsigned ( N , D ) Q : = 0 ; R : = N while 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 числителя  if  R  ≥  D  then  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 for  i  : =  n  −  1  ..  0  do  -- Например, 31..0 для 32 бит  R  : =  2  *  R  −  D  -- Пробное вычитание из сдвинутого значения (умножение на 2 является сдвигом в двоичном представлении)  if  R  >=  0  then  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 бит  if  R  >=  0  then  q ( i )  : =  + 1  R  : =  2  *  R  −  D  else  q ( i )  : =  − 1  R  : =  2  *  R  +  D  end  if end -- Примечание: N=числитель, D=знаменатель, n=#бит, R=частичный остаток, q(i)=бит #i частного.

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

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

Q  : =  Q  −  bit . 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-деление — популярный метод деления во многих реализациях микропроцессоров . ^{[5] [6]} Алгоритм назван в честь DW Sweeney из IBM , James E. Robertson из Университета Иллинойса и KD Tocher из Имперского колледжа Лондона . Они все разработали алгоритм независимо друг от друга примерно в одно и то же время (опубликован в феврале 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 single precision и 4 для форматов double precision и double extended . ${\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' // предварительно вычислить константы с той же точностью, что и D повторить  раз ${\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}$   // можно предварительно вычислить на основе фиксированного 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] использует итеративный процесс многократного умножения делимого и делителя на общий множитель F _i , выбранный таким образом, чтобы делитель сходился к 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, каждый Fi основан на 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]} Редукция Барретта использует степени 2 для значения Y , чтобы сделать деление на Y простым сдвигом вправо. ^[b]

В качестве конкретного примера арифметики с фиксированной точкой для 32-битных беззнаковых целых чисел деление на 3 можно заменить умножением на ⁠2863311531/2 ³³⁠ , умножение на 2863311531 ( шестнадцатеричное 0xAAAAAAAB) с последующим сдвигом вправо на 33 бита. Значение 2863311531 вычисляется как ⁠2 ³³/3⁠ , затем округляется вверх. Аналогично, деление на 10 может быть выражено как умножение на 3435973837 (0xCCCD) с последующим делением на 2 ³⁵ (или 35 правый битовый сдвиг). ^{[25] : стр. 230-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]

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

Когда выполняется операция деления, точное частное и остаток аппроксимируются, чтобы соответствовать пределам точности компьютера. Алгоритм деления гласит: ${\displaystyle q}$ ${\displaystyle r}$

${\displaystyle [a=bq+r]}$

где . ${\displaystyle 0\leq r<|b|}$

В арифметике с плавающей точкой частное представляется как , а остаток как , что приводит к ошибкам округления и : ${\displaystyle q}$ ${\displaystyle {\tilde {q}}}$ ${\displaystyle r}$ ${\displaystyle {\tilde {r}}}$ ${\displaystyle \epsilon _{q}}$ ${\displaystyle \epsilon _{q}}$ ${\displaystyle \epsilon _{r}}$

${\displaystyle [{\tilde {q}}=q+\epsilon _{q}][{\tilde {r}}=r+\epsilon _{r}]}$

Это округление вызывает небольшую ошибку, которая может распространяться и накапливаться в ходе последующих вычислений. Такие ошибки особенно выражены в итеративных процессах и при вычитании почти равных значений - говорят о потере значимости . Чтобы смягчить эти ошибки, применяются такие методы, как использование защитных цифр или арифметики более высокой точности. ^{[28] [29]}

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

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

Примечания

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

Ссылки

1. Родехэффер, Томас Л. (2008-08-26). Программное целочисленное деление (PDF) (технический отчет). Microsoft Research, Кремниевая долина.
2. Моррис, Джеймс Э.; Иневски, Кшиштоф (2017-11-22). Справочник по применению наноэлектронных устройств. CRC Press. ISBN 978-1-351-83197-0.
3. Шоу, Роберт Ф. (1950). «Арифметические операции в двоичном компьютере». Review of Scientific Instruments . 21 (8): 690. Bibcode : 1950RScI...21..687S. doi : 10.1063/1.1745692. ISSN  0034-6748. Архивировано из оригинала 28.02.2022 . Получено 28.02.2022 .
4. Флинн. "Stanford EE486 (Advanced Computer Arithmetic Division) – Chapter 5 Handout (Division)" (PDF) . Стэнфордский университет . Архивировано (PDF) из оригинала 2022-04-18 . Получено 2019-06-24 .
5. Харрис, Дэвид Л.; Оберман, Стюарт Ф.; Хоровиц, Марк А. (9 сентября 1998 г.). SRT Division: Architectures, Models, and Implementations (PDF) (Технический отчет). Стэнфордский университет. Архивировано (PDF) из оригинала 24 декабря 2016 г. . Получено 23 декабря 2016 г. .
6. Макканн, Марк; Пиппенджер, Николас (2005). «Алгоритмы разделения SRT как динамические системы». SIAM Journal on Computing . 34 (6): 1279–1301. CiteSeerX 10.1.1.72.6993 . doi :10.1137/S009753970444106X. hdl :2429/12179. Архивировано из оригинала 24.08.2022 . Получено 24.08.2022 . 
7. Cocke, John; Sweeney, DW (11 февраля 1957 г.), Высокоскоростная арифметика в параллельном устройстве (памятка компании), IBM, стр. 20, архивировано из оригинала 24 августа 2022 г. , извлечено 24 августа 2022 г.{{citation}}: CS1 maint: location missing publisher (link)
8. Робертсон, Джеймс (1958-09-01). "Новый класс методов цифрового деления". IRE Transactions on Electronic Computers . EC-7 (3). IEEE: 218–222. doi :10.1109/TEC.1958.5222579. hdl : 2027/uiuo.ark:/13960/t0gt7529c . Архивировано из оригинала 24.08.2022 . Получено 24.08.2022 .
9. Tocher, KD (1958-01-01). «Методы умножения и деления для автоматических двоичных компьютеров». The Quarterly Journal of Mechanics and Applied Mathematics . 11 (3): 364–384. doi :10.1093/qjmam/11.3.364. Архивировано из оригинала 24.08.2022 . Получено 24.08.2022 .
10. "Статистический анализ дефекта с плавающей точкой". Intel Corporation. 1994. Архивировано из оригинала 23 октября 2013 года . Получено 22 октября 2013 года .
11. Оберман, Стюарт Ф.; Флинн, Майкл Дж. (июль 1995 г.). Анализ алгоритмов деления и их реализации (PDF) (технический отчет). Стэнфордский университет. CSL-TR-95-675. Архивировано (PDF) из оригинала 17.05.2017 . Получено 23.12.2016 .
12. Goldschmidt, Robert E. (1964). Applications of Division by Convergence (PDF) (Thesis). M.Sc. dissertation. MIT OCLC  34136725. Архивировано (PDF) из оригинала 2015-12-10 . Получено 2015-09-15 .
13. "Авторы". IBM Journal of Research and Development . 11 : 125–127. 1967. doi :10.1147/rd.111.0125. Архивировано из оригинала 18 июля 2018 года.
14. Оберман, Стюарт Ф. (1999). "Алгоритмы деления с плавающей точкой и квадратного корня и их реализация в микропроцессоре AMD-K7" (PDF) . Труды 14-го симпозиума IEEE по компьютерной арифметике (Кат. № 99CB36336) . стр. 106–115. doi :10.1109/ARITH.1999.762835. ISBN 0-7695-0116-8. S2CID  12793819. Архивировано (PDF) из оригинала 2015-11-29 . Получено 2015-09-15 .
15. Содерквист, Питер; Лизер, Мириам (июль–август 1997 г.). «Деление и квадратный корень: выбор правильной реализации». IEEE Micro . 17 (4): 56–66. doi :10.1109/40.612224.
16. SF Anderson, JG Earle, RE Goldschmidt, DM Powers. IBM 360/370 model 91: floating-point execution unit , IBM Journal of Research and Development , январь 1997 г.
17. Guy, Even; Peter, Siedel; Ferguson, Warren (1 февраля 2005 г.). «Параметрический анализ ошибок алгоритма деления Гольдшмидта». Журнал компьютерных и системных наук . 70 (1): 118–139. doi : 10.1016/j.jcss.2004.08.004 .
18. Хассельстрём, Карл (2003). Быстрое разделение больших целых чисел: сравнение алгоритмов (PDF) (диссертация на степень магистра компьютерных наук). Королевский технологический институт. Архивировано из оригинала (PDF) 8 июля 2017 года . Получено 08.07.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 . doi :10.1145/773473.178249. Архивировано (PDF) из оригинала 2019-06-06 . Получено 2015-12-08 . 
22. Möller, Niels; Granlund, Torbjörn (февраль 2011 г.). «Улучшенное деление на инвариантные целые числа» (PDF) . IEEE Transactions on Computers . 60 (2): 165–175. doi :10.1109/TC.2010.143. S2CID  13347152. Архивировано (PDF) из оригинала 22.12.2015 . Получено 08.12.2015 .
23. funny_fish. «Труд деления (Эпизод III): Более быстрое беззнаковое деление на константы» Архивировано 08.01.2022 на Wayback Machine . 2011.
24. funny_fish. "libdivide, оптимизированное целочисленное деление". Архивировано из оригинала 23 ноября 2021 г. Получено 6 июля 2021 г.
25. Уоррен-младший, Генри С. (2013). Hacker's Delight (2-е изд.). Addison Wesley - Pearson Education, Inc. ISBN  978-0-321-84268-8.
26. Лабудд, Роберт А.; Головченко, Николай; Ньютон, Джеймс; и Паркер, Дэвид; Massmind: «Двоичное деление на константу». Архивировано 09.01.2022 на Wayback Machine
27. Vowels, RA (1992). «Деление на 10». Australian Computer Journal . 24 (3): 81–85.
28. Л. Попяк, Джеффри (июнь 2000 г.). «Ошибка округления». Университет Дрекселя .
29. "9. Машинные числа, ошибка округления и распространение ошибок". Колледж Чарльстона . 8 февраля 2021 г.

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

• Savard, John JG (2018) [2006]. "Advanced Arithmetic Techniques". quadibloc . Архивировано из оригинала 2018-07-03 . Получено 2018-07-16 .