Jump to content

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

(Перенаправлено с отдела восстановления )

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

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

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

Обсуждение будет относиться к форме , где

это вход, и

это выход.

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

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

Самый простой алгоритм деления, исторически включенный в алгоритм наибольшего общего делителя , представленный в » Евклида «Началах , Книга 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]

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

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

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

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

Ньютон-Рафсон использует метод Ньютона , чтобы найти обратную величину. и умножьте это обратное значение на найти последнее частное .

Этапы разделения Ньютона-Рафсона:

  1. Рассчитать смету для взаимного делителя .
  2. Вычисляйте последовательно более точные оценки взаимного. Именно здесь используется метод Ньютона-Рафсона как таковой.
  3. Вычислите частное, умножив делимое на обратную величину делителя: .

Чтобы применить метод Ньютона для нахождения обратной величины , необходимо найти функцию у которого есть ноль в . Очевидная такая функция , но итерация Ньютона-Рафсона для этого бесполезна, поскольку ее нельзя вычислить, не зная обратного значения (более того, он пытается вычислить точную обратную величину за один шаг, а не допускает итеративные улучшения). Функция, которая работает, это , для которого итерация Ньютона–Рафсона дает

который можно вычислить из используя только умножение и вычитание или используя два слитых умножения и сложения .

С вычислительной точки зрения выражения и не эквивалентны. Чтобы получить результат с точностью до 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 :

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

  1. Сгенерируйте оценку для коэффициента умножения F i .
  2. Умножьте делимое и делитель на F i .
  3. Если делитель достаточно близок к 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]

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

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

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

См. также

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

Примечания

[ редактировать ]
  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: отсутствует местоположение издателя ( ссылка )
  8. ^ Робертсон, Джеймс (1 сентября 1958 г.). «Новый класс методов цифрового деления» . IRE-транзакции на электронных компьютерах . ИС-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-K7» (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. ^ Jump up to: а б Гай, Эвен; Питер, Зидель; Фергюсон, Уоррен (1 февраля 2005 г.). «Параметрический анализ ошибок алгоритма деления Гольдшмидта» . Журнал компьютерных и системных наук . 70 (1): 118–139. дои : 10.1016/j.jcss.2004.08.004 .
  18. ^ Хассельстрем, Карл (2003). Быстрое деление больших целых чисел: сравнение алгоритмов (PDF) (диссертация на степень магистра компьютерных наук). Королевский технологический институт. Архивировано из оригинала (PDF) 8 июля 2017 года . Проверено 08 июля 2017 г.
  19. ^ Иоахим Циглер, Кристоф Бурникель (1998), Отдел быстрой рекурсии , Институт компьютерных наук Макса Планка, заархивировано из оригинала 26 апреля 2011 г. , получено 10 сентября 2021 г. {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
  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-е изд.). Аддисон Уэсли - Pearson Education, Inc. ISBN  978-0-321-84268-8 .
  26. ^ ЛаБудд, Роберт А.; Головченко, Николай; Ньютон, Джеймс; и Паркер, Дэвид; Massmind: «Двоичное деление на константу». Архивировано 9 января 2022 г. на Wayback Machine.
  27. ^ Гласные, РА (1992). «Деление на 10». Австралийский компьютерный журнал . 24 (3): 81–85.

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

[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 52f66618fd077807e07f1a713c91b73d__1719664560
URL1:https://arc.ask3.ru/arc/aa/52/3d/52f66618fd077807e07f1a713c91b73d.html
Заголовок, (Title) документа по адресу, URL1:
Division algorithm - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)