Алгоритм деления
Алгоритм деления — это алгоритм , который по двум целым числам N и D (соответственно числителю и знаменателю) вычисляет их частное и/или остаток — результат евклидова деления . Некоторые из них наносятся вручную, а другие используются с помощью цифровых схем и программного обеспечения.
Алгоритмы деления делятся на две основные категории: медленное деление и быстрое деление. Алгоритмы медленного деления производят одну цифру конечного частного за итерацию. Примеры медленного деления включают восстановление , невыполняющееся восстановление, невосстановление и деление SRT . Методы быстрого деления начинаются с близкого приближения к конечному частному и выдают вдвое больше цифр конечного частного на каждой итерации. [1] Алгоритмы Ньютона-Рафсона и Гольдшмидта попадают в эту категорию.
Варианты этих алгоритмов позволяют использовать быстрые алгоритмы умножения . В результате для больших целых чисел компьютерное время , необходимое для деления, с точностью до постоянного коэффициента такое же, как и время, необходимое для умножения, независимо от того, какой алгоритм умножения используется.
Обсуждение будет относиться к форме , где
- N = числитель (дивиденд)
- D = знаменатель (делитель)
это вход, и
это выход.
Деление повторным вычитанием
[ редактировать ]Самый простой алгоритм деления, исторически включенный в алгоритм наибольшего общего делителя , представленный в » Евклида «Началах , Книга VII, Предложение 1, находит остаток по двум положительным целым числам, используя только вычитания и сравнения:
R := N
Q := 0
while R ≥ D do
R := R − D
Q := Q + 1
end
return (Q,R)
Доказательство того, что частное и остаток существуют и уникальны (описано в разделе «Евклидово деление »), приводит к созданию полного алгоритма деления, применимого как к отрицательным, так и к положительным числам, с использованием сложения, вычитания и сравнения:
function divide(N, D)
if D = 0 then error(DivisionByZero) end
if D < 0 then (Q, R) := divide(N, −D); return (−Q, R) end
if N < 0 then
(Q,R) := divide(−N, D)
if R = 0 then return (−Q, 0)
else return (−Q − 1, D − R) end
end
-- At this point, N ≥ 0 and 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 -- Initialize quotient and remainder to zero
R := 0
for i := n − 1 .. 0 do -- Where n is number of bits in N
R := R << 1 -- Left-shift R by 1 bit
R(0) := N(i) -- Set the least-significant bit of R equal to bit i of the numerator
if R ≥ D then
R := R − D
Q(i) := 1
end
end
Пример
[ редактировать ]Если взять N=1100 2 (12 10 ) и D=100 2 (4 10 )
Шаг 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 2 (3 10 ) и R=0.
Методы медленного деления
[ редактировать ]Все методы медленного деления основаны на стандартном рекуррентном уравнении. [2]
где:
- 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 and D need twice the word width of N and Q
for i := n − 1 .. 0 do -- For example 31..0 for 32 bits
R := 2 * R − D -- Trial subtraction from shifted value (multiplication by 2 is a shift in binary representation)
if R >= 0 then
q(i) := 1 -- Result-bit 1
else
q(i) := 0 -- Result-bit 0
R := R + D -- New partial remainder is (restored) shifted value
end
end
-- Where: N = numerator, D = denominator, n = #bits, R = partial remainder, q(i) = bit #i of quotient
Неработающее восстанавливающее деление похоже на восстанавливающее деление, за исключением того, что значение 2R сохраняется, поэтому D не нужно добавлять обратно в случае R < 0.
Невосстанавливающееся деление
[ редактировать ]Деление без восстановления использует набор цифр {-1, 1} для цифр частного вместо {0, 1}. Алгоритм более сложен, но при аппаратной реализации имеет то преимущество, что для каждого бита частного требуется только одно решение и сложение/вычитание; после вычитания нет этапа восстановления, [3] что потенциально сокращает количество операций почти вдвое и позволяет выполнять их быстрее. [4] Основной алгоритм двоичного (основание 2) невосстанавливающегося деления неотрицательных чисел:
R := N
D := D << n -- R and D need twice the word width of N and Q
for i = n − 1 .. 0 do -- for example 31..0 for 32 bits
if R >= 0 then
q(i) := +1
R := 2 * R − D
else
q(i) := −1
R := 2 * R + D
end if
end
-- Note: N=numerator, D=denominator, n=#bits, R=partial remainder, q(i)=bit #i of quotient.
Следуя этому алгоритму, частное имеет нестандартную форму, состоящую из цифр -1 и +1. Эту форму необходимо преобразовать в двоичную, чтобы получить окончательное частное. Пример:
Преобразуйте следующее частное в набор цифр {0,1}: | |
Начинать: | |
1. Образуйте положительный член: | |
2. Замаскируйте отрицательный термин*: | |
3. Вычтите: : | |
*.(Знаковая двоичная запись с дополнением до единиц без дополнения до двух ) |
Если -1 цифры хранятся как нули (0), как обычно, тогда является и вычисления тривиально: выполнить дополнение единиц (побитовое дополнение) к оригиналу .
Q := Q − bit.bnot(Q) -- Appropriate if −1 digits in Q are represented as zeros as is common.
Наконец, частные, вычисленные с помощью этого алгоритма, всегда нечетны, а остаток в R находится в диапазоне −D ≤ R <D. Например, 5/2 = 3 R −1. Чтобы преобразовать в положительный остаток, выполните один шаг восстановления после преобразования Q из нестандартной формы в стандартную:
if R < 0 then
Q := Q − 1
R := R + D -- Needed only if the remainder is of interest.
end if
Фактический остаток равен 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]
Методы быстрого деления
[ редактировать ]Подразделение Ньютона-Рафсона
[ редактировать ]Ньютон-Рафсон использует метод Ньютона , чтобы найти обратную величину. и умножьте это обратное значение на найти последнее частное .
Этапы разделения Ньютона-Рафсона:
- Рассчитать смету для взаимного делителя .
- Вычисляйте последовательно более точные оценки взаимного. Именно здесь используется метод Ньютона-Рафсона как таковой.
- Вычислите частное, умножив делимое на обратную величину делителя: .
Чтобы применить метод Ньютона для нахождения обратной величины , необходимо найти функцию у которого есть ноль в . Очевидная такая функция , но итерация Ньютона-Рафсона для этого бесполезна, поскольку ее нельзя вычислить, не зная обратного значения (более того, он пытается вычислить точную обратную величину за один шаг, а не допускает итеративные улучшения). Функция, которая работает, это , для которого итерация Ньютона–Рафсона дает
который можно вычислить из используя только умножение и вычитание или используя два слитых умножения и сложения .
С вычислительной точки зрения выражения и не эквивалентны. Чтобы получить результат с точностью до 2 n бит при использовании второго выражения, необходимо вычислить произведение между и с двойной заданной точностью ( n бит). [ нужна ссылка ] Напротив, продукт между и необходимо вычислять только с точностью до n бит, поскольку первые n бит (после двоичной точки) являются нулями.
Если ошибка определяется как , затем:
Это возведение ошибки на каждом шаге итерации в квадрат – так называемая квадратичная сходимость метода Ньютона–Рафсона – приводит к тому, что количество правильных цифр в результате примерно удваивается для каждой итерации . Это свойство становится чрезвычайно ценным, когда задействованные числа иметь много цифр (например, в большой целочисленной области). Но это также означает, что первоначальная сходимость метода может быть сравнительно медленной, особенно если первоначальная оценка выбран неудачно.
Для подзадачи выбора начальной оценки , удобно применить побитовый сдвиг к делителю D, чтобы масштабировать его так, чтобы 0,5 ≤ D ≤ 1; применяя тот же битовый сдвиг к числителю N , можно гарантировать, что частное не изменится. Тогда можно было бы использовать линейное приближение в виде
для инициализации Ньютона-Рафсона. Минимизировать максимум абсолютного значения ошибки данного приближения на интервале , следует использовать
Коэффициенты линейного приближения определяются следующим образом. Абсолютное значение ошибки . Минимум максимального абсолютного значения погрешности определяется теоремой Чебышева об эквиколебаниях, примененной к . Локальный минимум происходит, когда , которое имеет решение . Функция в этом минимуме должна иметь противоположный знак, что и функция в конечных точках, а именно: . Два уравнения с двумя неизвестными имеют единственное решение и , а максимальная ошибка равна . При использовании этого приближения абсолютная величина ошибки начального значения меньше
Можно сгенерировать полиномиальную аппроксимацию степени больше 1, вычисляя коэффициенты с помощью алгоритма Ремеза . Компромисс заключается в том, что первоначальное предположение требует большего количества вычислительных циклов, но, будем надеяться, в обмен на меньшее количество итераций Ньютона-Рафсона.
Поскольку для этого метода сходимость в точности квадратичная, отсюда следует, что
шагов достаточно, чтобы вычислить значение до бинарные места. Это значение равно 3 для форматов одинарной точности IEEE и 4 для форматов двойной точности и расширенного формата двойной точности .
Псевдокод
[ редактировать ]Следующее вычисляет частное N и D с точностью до P двоичных разрядов:
Express D as M × 2e where 1 ≤ M < 2 (standard floating point representation)
D' := D / 2e+1 // scale between 0.5 and 1, can be performed with bit shift / exponent subtraction
N' := N / 2e+1
X := 48/17 − 32/17 × D' // precompute constants with same precision as D
repeat times // can be precomputed based on fixed P
X := X + X × (1 - D' × X)
end
return N' × X
Например, для деления с плавающей запятой двойной точности этот метод использует 10 умножений, 9 сложений и 2 сдвига.
Вариант разделения Ньютона – Рафсона
[ редактировать ]Метод деления Ньютона-Рафсона можно изменить, чтобы он стал немного быстрее, следующим образом. После сдвига N и D так, чтобы D находился в [0,5, 1,0], инициализируйте с помощью
Это наилучшее квадратичное приближение к 1/ D , которое дает абсолютное значение ошибки меньше или равное 1/99. Ошибка выбрана так, чтобы ошибка была равна перемасштабированному полиному Чебышева третьего порядка первого рода. Коэффициенты должны быть заранее рассчитаны и жестко закодированы.
Затем в цикле используйте итерацию, которая кубизирует ошибку.
Термин Y ⋅ E является новым.
Если цикл выполняется до тех пор, пока X не согласуется с 1/ D на своих ведущих битах P , то количество итераций будет не более
сколько раз 99 нужно возложить в куб, чтобы получить 2 П +1 . Затем
это частное к P битам.
Использование полиномов более высокой степени при инициализации или итерации приводит к снижению производительности, поскольку необходимые дополнительные умножения лучше потратить на выполнение большего количества итераций.
Гольдшмидтское подразделение
[ редактировать ]Гольдшмидтское подразделение [12] (по мотивам Роберта Эллиота Гольдшмидта) [13] использует итерационный процесс многократного умножения делимого и делителя на общий коэффициент F i , выбранный так, чтобы делитель сходился к 1. Это заставляет делимое сходиться к искомому частному Q :
Шаги подразделения Гольдшмидта:
- Сгенерируйте оценку для коэффициента умножения F i .
- Умножьте делимое и делитель на F i .
- Если делитель достаточно близок к 1, верните делимое, в противном случае перейдите к шагу 1.
Предполагая, что N / D масштабировано так, что 0 < D <1, каждый F i основан на D :
Умножение дивиденда и делителя на коэффициент дает:
После достаточного числа k итераций .
Метод Гольдшмидта используется в процессорах AMD Athlon и более поздних моделях. [14] [15] Он также известен как алгоритм Андерсона Эрла Голдшмидта Пауэрса (AEGP) и реализуется различными процессорами IBM. [16] [17] Хотя он сходится с той же скоростью, что и реализация Ньютона-Рафсона, одним из преимуществ метода Гольдшмидта является то, что умножения в числителе и знаменателе могут выполняться параллельно. [17]
Биномиальная теорема
[ редактировать ]Метод Гольдшмидта можно использовать с факторами, допускающими упрощения по биномиальной теореме . Предположим был масштабирован в степени двойки так, что . Мы выбираем и . Это дает
- .
Через n шагов , знаменатель можно округлить до 1 с относительной погрешностью
что является максимальным при когда , что обеспечивает минимальную точность двоичные цифры.
Методы больших целых чисел
[ редактировать ]Методы, предназначенные для аппаратной реализации, обычно не масштабируются до целых чисел с тысячами или миллионами десятичных цифр; они часто возникают, например, при модульном сокращении криптографии . Для этих больших целых чисел более эффективные алгоритмы деления преобразуют задачу, используя небольшое количество умножений, что затем можно выполнить с помощью асимптотически эффективного алгоритма умножения, такого как алгоритм Карацубы , умножение Тума-Кука или алгоритм Шёнхаге-Штрассена . В результате вычислительная сложность деления имеет тот же порядок (с точностью до мультипликативной константы), что и умножение. Примеры включают приведение к умножению методом Ньютона, как описано выше , [18] а также немного более быстрая дивизия Бурникеля-Циглера , [19] редукции Барретта и редукции Монтгомери . Алгоритмы [20] [ нужна проверка ] Метод Ньютона особенно эффективен в сценариях, где необходимо многократно делить на один и тот же делитель, поскольку после первоначального обращения Ньютона для каждого деления требуется только одно (усеченное) умножение.
Деление на константу
[ редактировать ]Деление на константу 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 , но «достаточно близко», чтобы ошибка, вносимая аппроксимацией, составляла в битах, которые отбрасываются в результате операции сдвига. [21] [22] [23] Сокращение Барретта использует степени 2 для значения Y, чтобы сделать деление на Y простым сдвигом вправо. [б]
В качестве конкретного примера арифметики с фиксированной запятой для 32-битных целых чисел без знака деление на 3 можно заменить умножением на 2863311531 / 2 33 , умножение на 2863311531 ( шестнадцатеричное 0xAAAAAAAB), за которым следует сдвиг вправо на 33 бита. Значение 2863311531 рассчитывается как 2 33 / 3 , затем округляем в большую сторону. Аналогично, деление на 10 можно выразить как умножение на 3435973837 (0xCCCCCCCD) с последующим делением на 2. 35 (или сдвиг вправо на 35 бит). [25] : стр. 230-234 OEIS предоставляет последовательности констант для умножения как A346495 и для сдвига вправо как A346496 .
Для общего деления x -битного беззнакового целого числа, где делитель D не является степенью 2, следующее тождество преобразует деление в двух x сложение/вычитание -битов, умножение одного x -бита на x - бит (где только верхняя половина результат используется) и несколько смен, после предварительного расчета и :
В некоторых случаях деление на константу можно выполнить еще за меньшее время, превратив «умножение на константу» в серию сдвигов и сложений или вычитаний . [26] Особый интерес представляет деление на 10, для которого получается точное частное с остатком, если необходимо. [27]
Ошибка округления
[ редактировать ]Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( сентябрь 2012 г. ) |
Ошибка округления может быть внесена операциями деления из-за ограниченной точности .
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Несмотря на то, насколько «небольшую» проблему вызывает оптимизация, эта взаимная оптимизация в современных компиляторах все еще обычно скрывается за флагом «быстрой математики» , поскольку она неточна.
- ^ Современные компиляторы обычно выполняют эту оптимизацию целочисленного умножения и сдвига; однако для константы, известной только во время выполнения, программа должна сама реализовать оптимизацию. [24]
Ссылки
[ редактировать ]- ^ Родехеффер, Томас Л. (26 августа 2008 г.). Software Integer Division (PDF) (Технический отчет). Microsoft Research, Кремниевая долина.
- ^ Моррис, Джеймс Э.; Иневский, Кшиштоф (22 ноября 2017 г.). Справочник по применению наноэлектронных устройств . ЦРК Пресс. ISBN 978-1-351-83197-0 .
- ^ Шоу, Роберт Ф. (1950). «Арифметические операции в двоичной машине» . Обзор научных инструментов . 21 (8): 690. Бибкод : 1950RScI...21..687S . дои : 10.1063/1.1745692 . ISSN 0034-6748 . Архивировано из оригинала 28 февраля 2022 г. Проверено 28 февраля 2022 г.
- ^ Флинн. «Stanford EE486 (Отдел продвинутой компьютерной арифметики) - Раздаточный материал главы 5 (Отдел)» (PDF) . Стэнфордский университет . Архивировано (PDF) из оригинала 18 апреля 2022 г. Проверено 24 июня 2019 г.
- ^ Харрис, Дэвид Л.; Оберман, Стюарт Ф.; Горовиц, Марк А. (9 сентября 1998 г.). Отдел SRT: Архитектура, модели и реализации (PDF) (Технический отчет). Стэнфордский университет. Архивировано (PDF) из оригинала 24 декабря 2016 года . Проверено 23 декабря 2016 г.
- ^ Макканн, Марк; Пиппенджер, Николас (2005). «Алгоритмы разделения СТО как динамические системы» . SIAM Journal по вычислительной технике . 34 (6): 1279–1301. CiteSeerX 10.1.1.72.6993 . дои : 10.1137/S009753970444106X . Архивировано из оригинала 24 августа 2022 г. Проверено 24 августа 2022 г.
- ^ Кок, Джон; Суини, Д.В. (11 февраля 1957 г.), Высокоскоростная арифметика в параллельном устройстве (Company Memo), IBM, стр. 20, заархивировано из оригинала 24 августа 2022 года , получено 24 августа 2022 года.
{{citation}}
: CS1 maint: отсутствует местоположение издателя ( ссылка ) - ^ Робертсон, Джеймс (1 сентября 1958 г.). «Новый класс методов цифрового деления» . IRE-транзакции на электронных компьютерах . ИС-7 (3). ИИЭР: 218–222. дои : 10.1109/TEC.1958.5222579 . hdl : 2027/uiuo.ark:/13960/t0gt7529c . Архивировано из оригинала 24 августа 2022 г. Проверено 24 августа 2022 г.
- ^ Точер, К.Д. (1 января 1958 г.). «Техника умножения и деления для автоматических двоичных компьютеров» . Ежеквартальный журнал механики и прикладной математики . 11 (3): 364–384. дои : 10.1093/qjmam/11.3.364 . Архивировано из оригинала 24 августа 2022 г. Проверено 24 августа 2022 г.
- ^ «Статистический анализ ошибок с плавающей запятой» . Корпорация Интел. 1994. Архивировано из оригинала 23 октября 2013 года . Проверено 22 октября 2013 г.
- ^ Оберман, Стюарт Ф.; Флинн, Майкл Дж. (июль 1995 г.). Анализ алгоритмов и реализаций разделения (PDF) (Технический отчет). Стэнфордский университет. CSL-TR-95-675. Архивировано (PDF) из оригинала 17 мая 2017 г. Проверено 23 декабря 2016 г.
- ^ Гольдшмидт, Роберт Э. (1964). Применение деления по сходимости (PDF) (Диссертация). Магистр наук диссертация. MIT OCLC 34136725 . Архивировано (PDF) из оригинала 10 декабря 2015 г. Проверено 15 сентября 2015 г.
- ^ «Авторы» . Журнал исследований и разработок IBM . 11 : 125–127. 1967. дои : 10.1147/рд.111.0125 . Архивировано из оригинала 18 июля 2018 года.
- ^ Оберман, Стюарт Ф. (1999). «Алгоритмы деления с плавающей запятой и квадратного корня и их реализация в микропроцессоре AMD-K7» (PDF) . Материалы 14-го симпозиума IEEE по компьютерной арифметике (кат. № 99CB36336) . стр. 106–115. дои : 10.1109/ARITH.1999.762835 . ISBN 0-7695-0116-8 . S2CID 12793819 . Архивировано (PDF) из оригинала 29 ноября 2015 г. Проверено 15 сентября 2015 г.
- ^ Содерквист, Питер; Лизер, Мириам (июль – август 1997 г.). «Деление и квадратный корень: выбор правильной реализации» . IEEE микро . 17 (4): 56–66. дои : 10.1109/40.612224 .
- ^ С.Ф. Андерсон, Дж.Г. Эрл, Р.Е. Гольдшмидт, Д.М. Пауэрс. IBM 360/370 model 91: исполнительный блок с плавающей запятой , IBM Journal of Research and Development , январь 1997 г.
- ^ Jump up to: а б Гай, Эвен; Питер, Зидель; Фергюсон, Уоррен (1 февраля 2005 г.). «Параметрический анализ ошибок алгоритма деления Гольдшмидта» . Журнал компьютерных и системных наук . 70 (1): 118–139. дои : 10.1016/j.jcss.2004.08.004 .
- ^ Хассельстрем, Карл (2003). Быстрое деление больших целых чисел: сравнение алгоритмов (PDF) (диссертация на степень магистра компьютерных наук). Королевский технологический институт. Архивировано из оригинала (PDF) 8 июля 2017 года . Проверено 08 июля 2017 г.
- ^ Иоахим Циглер, Кристоф Бурникель (1998), Отдел быстрой рекурсии , Институт компьютерных наук Макса Планка, заархивировано из оригинала 26 апреля 2011 г. , получено 10 сентября 2021 г.
{{citation}}
: CS1 maint: отсутствует местоположение издателя ( ссылка ) - ^ Барретт, Пол (1987). «Реализация алгоритма шифрования с открытым ключом Ривеста Шамира и Адлемана на стандартном процессоре цифровых сигналов» . Труды о достижениях в криптологии --- CRYPTO '86 . Лондон, Великобритания: Springer-Verlag. стр. 311–323. ISBN 0-387-18047-8 .
- ^ Гранлунд, Торбьёрн; Монтгомери, Питер Л. (июнь 1994 г.). «Деление на инвариантные целые числа с использованием умножения» (PDF) . Уведомления SIGPLAN . 29 (6): 61–72. CiteSeerX 10.1.1.1.2556 . дои : 10.1145/773473.178249 . Архивировано (PDF) из оригинала 6 июня 2019 г. Проверено 8 декабря 2015 г.
- ^ Мёллер, Нильс; Гранлунд, Торбьорн (февраль 2011 г.). «Улучшенное деление инвариантными целыми числами» (PDF) . Транзакции IEEE на компьютерах . 60 (2): 165–175. дои : 10.1109/TC.2010.143 . S2CID 13347152 . Архивировано (PDF) из оригинала 22 декабря 2015 г. Проверено 8 декабря 2015 г.
- ^ смешная_рыба. «Труд разделения (Эпизод III): более быстрое деление без знака константами». Архивировано 8 января 2022 г. в Wayback Machine . 2011.
- ^ смешная_рыба. «libdivide, оптимизированное целочисленное деление» . Архивировано из оригинала 23 ноября 2021 года . Проверено 6 июля 2021 г.
- ^ Уоррен младший, Генри С. (2013). Хакерское наслаждение (2-е изд.). Аддисон Уэсли - Pearson Education, Inc. ISBN 978-0-321-84268-8 .
- ^ ЛаБудд, Роберт А.; Головченко, Николай; Ньютон, Джеймс; и Паркер, Дэвид; Massmind: «Двоичное деление на константу». Архивировано 9 января 2022 г. на Wayback Machine.
- ^ Гласные, РА (1992). «Деление на 10». Австралийский компьютерный журнал . 24 (3): 81–85.
Дальнейшее чтение
[ редактировать ]- Савард, Джон Дж. Г. (2018) [2006]. «Продвинутые арифметические методы» . четырехблок . Архивировано из оригинала 3 июля 2018 г. Проверено 16 июля 2018 г.