Алгоритм деления - Division algorithm
А алгоритм деления является алгоритм который, учитывая два целых числа N и D, вычисляет их частное и / или остаток, результат Евклидово деление. Некоторые применяются вручную, а другие используются в цифровых схемах и программном обеспечении.
Алгоритмы деления делятся на две основные категории: медленное деление и быстрое деление. Алгоритмы медленного деления производят одну цифру окончательного частного за итерацию. Примеры медленного деления включают восстановление, неработающее восстановление, невосстанавливающий, и SRT разделение. Методы быстрого деления начинаются с близкого приближения к конечному частному и производят вдвое больше цифр конечного частного на каждой итерации. Ньютон – Рафсон и Гольдшмидт алгоритмы попадают в эту категорию.
Варианты этих алгоритмов позволяют быстро использовать алгоритмы умножения. Это приводит к тому, что для больших целых чисел компьютерное время необходимое для деления такое же, с точностью до постоянного множителя, что и время, необходимое для умножения, независимо от того, какой алгоритм умножения используется.
Обсуждение будет относиться к форме , куда
- N = Числитель (делимое)
- D = Знаменатель (делитель)
это вход, а
- Q = Частное
- р = Остаток
это выход.
Деление повторным вычитанием
Простейший алгоритм деления, исторически включенный в наибольший общий делитель алгоритм представлен в Евклида Элементы Книга VII, Предложение 1, находит остаток от двух положительных целых чисел, используя только вычитания и сравнения:
пока N ≥ D делать N := N − Dконецвернуть N
Доказательство того, что фактор и остаток существуют и единственны (описано в Евклидово деление ) приводит к полному алгоритму деления с использованием сложений, вычитаний и сравнений:
функция разделять(N, D) если D = 0 тогда ошибка(Деление на ноль) конец если D < 0 тогда (Q, р) := разделять(N, −D); вернуть (−Q, р) конец если N < 0 тогда (Q,р) := разделять(−N, D) если р = 0 тогда вернуть (−Q, 0) еще вернуть (−Q − 1, D − р) конец конец - В этот момент N ≥ 0 и D> 0 вернуть div_unsigned(N, D)конец функция div_unsigned(N, D) Q := 0; р := N пока р ≥ D делать Q := Q + 1 р := р − D конец вернуть (Q, р)конец
Эта процедура всегда дает R ≥ 0. Хотя она очень проста, она требует Ω (Q) шагов, поэтому она экспоненциально медленнее, чем даже алгоритмы медленного деления, такие как деление в столбик. Это полезно, если известно, что Q невелик ( алгоритм, чувствительный к выходу ) и может служить исполняемой спецификацией.
Длинное деление
Длинное деление - это стандартный алгоритм, используемый для ручного деления многозначных чисел, выраженных в десятичной системе счисления. Он постепенно сдвигается от левого края делимого к правому, вычитая максимально возможное кратное делителя (на уровне цифр) на каждом этапе; тогда кратные становятся цифрами частного, а окончательная разница становится остатком.
При использовании с двоичным основанием системы счисления этот метод формирует основу для (беззнакового) целочисленного деления с алгоритмом остатка ниже. Короткое деление - это сокращенная форма деления в столбик, подходящая для однозначных делителей. Разбивка - также известный как метод частичных частных или метод палача - это менее эффективная форма длинного деления, которую легче понять. Позволяя вычитать больше кратных, чем то, что есть в настоящее время на каждом этапе, можно также разработать более свободный вариант длинного деления.[1]
Целочисленное деление (без знака) с остатком
Следующий алгоритм, двоичная версия знаменитого длинное деление, разделит N к D, помещая частное в Q а остальное в р. В следующем коде все значения рассматриваются как целые числа без знака.
если D = 0 тогда ошибка(DivisionByZeroException) конецQ := 0 - Инициализировать частное и остаток до нуляр := 0 за я := п − 1 .. 0 делать - Где n - количество бит в N р := р << 1 - Сдвиг влево R на 1 бит р(0) := N(я) - Установить младший бит R равным i-му биту числителя если р ≥ D тогда р := р − D Q(я) := 1 конецконец
пример
Если взять N = 11002 (1210) и D = 1002 (410)
Шаг 1: Установить R = 0 и Q = 0
Шаг 2: Возьмем i = 3 (на единицу меньше, чем количество бит в N)
Шаг 3: R = 00 (сдвиг влево на 1)
Шаг 4: R = 01 (установка R (0) на N (i))
Шаг 5: R
Шаг 2: Установить i = 2
Шаг 3: R = 010
Шаг 4: R = 011
Шаг 5: R
Шаг 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 = 112 (310) и R = 0.
Методы медленного деления
Все методы медленного деления основаны на стандартном рекуррентном уравнении. [2]
- ,
куда:
- рj это j-й частичный остаток от деления
- B это основание (база, обычно 2 внутри компьютеров и калькуляторов)
- q п − (j + 1) цифра частного в позиции п− (j + 1), где позиции цифр пронумерованы от наименее значимого 0 до наиболее значимого п−1
- п количество цифр в частном
- D это делитель
Восстановление деления
Реставрационное подразделение работает на фиксированная точка дробные числа и зависит от предположения 0 < D < N.[нужна цитата ]
Частные цифры q формируются из набора цифр {0,1}.
Базовый алгоритм двоичного (основание 2) восстанавливающего деления:
р := ND := D << п - R и D должны вдвое превышать ширину слова N и Qза я := п − 1 .. 0 делать - Например 31..0 для 32 бит р := 2 * р − D - Пробное вычитание из сдвинутого значения (умножение на 2 - это сдвиг в двоичном представлении) если р ≥ 0 тогда q(я) := 1 - бит результата 1 еще q(я) := 0 - Бит результата 0 р := р + D - Новый частичный остаток (восстанавливается) смещённое значение конецконец- Где: N = числитель, D = знаменатель, n = # бит, R = частичный остаток, q (i) = бит #i частного
Вышеупомянутый восстанавливающий алгоритм деления может избежать этапа восстановления, сохранив смещенное значение 2.р перед вычитанием в дополнительном регистре Т (т.е. Т = р << 1) и копировальный аппарат Т к р когда результат вычитания 2р − D отрицательный.
Неработающее восстанавливающее деление аналогично восстанавливающему делению, за исключением того, что сохраняется значение 2R, поэтому D не нужно добавлять обратно в случае R <0.
Невосстанавливающееся подразделение
Невосстанавливающееся деление использует набор цифр {-1, 1} для частных цифр вместо {0, 1}. Алгоритм более сложен, но при аппаратной реализации имеет то преимущество, что существует только одно решение и сложение / вычитание на бит частного; после вычитания нет шага восстановления, который потенциально сокращает количество операций наполовину и позволяет выполнять их быстрее.[3] Базовый алгоритм двоичного (основание 2) невосстанавливающего деления неотрицательных чисел:
р := ND := D << п - R и D должны вдвое превышать ширину слова N и Qза я = п − 1 .. 0 делать - например 31..0 для 32 бит если р >= 0 тогда q[я] := +1 р := 2 * р − D еще q[я] := −1 р := 2 * р + D конец есликонец - Примечание: N = числитель, D = знаменатель, n = # битов, R = частичный остаток, q (i) = бит #i частного.
Следуя этому алгоритму, частное находится в нестандартной форме, состоящей из цифр -1 и +1. Эта форма должна быть преобразована в двоичную, чтобы получить окончательное частное. Пример:
Преобразуйте следующее частное в набор цифр {0,1}: | |
Начните: | |
1. Сформируйте положительный термин: | |
2. Замаскируйте отрицательный термин *: | |
3. Вычтите: : | |
*. (Двоичная запись со знаком Дополнение к одному без Два дополнения ) |
Если -1 цифра сохраняются как нули (0), как обычно, то является и вычисления тривиально: выполнить дополнение до единицы (побитовое дополнение) к оригиналу .
Q := Q − кусочек.bnot(Q) * Подходящее если −1 Цифры в Q находятся Представлено так как нули так как является общий.
Наконец, частные, вычисленные этим алгоритмом, всегда нечетные, а остаток в R находится в диапазоне -D ≤ R
если р < 0 тогда Q := Q − 1 р := р + D - Требуется только в том случае, если Остаток представляет интерес.конец если
Фактический остаток равен R >> n. (Как и в случае с восстанавливающим делением, младшие биты R используются с той же скоростью, что и биты частного Q, и обычно для обоих используется один регистр сдвига.)
Отделение СТО
Названный в честь своих создателей (Суини, Робертсон и Точер), разделение СТО является популярным методом разделения во многих странах. микропроцессор реализации.[4][5] Разделение SRT аналогично разделению без восстановления, но в нем используется Справочная таблица на основе делимого и делителя для определения каждой частной цифры.
Наиболее существенная разница в том, что избыточное представление используется для частного. Например, при реализации SRT деления по основанию 4, каждая цифра частного выбирается из пять возможности: {−2, −1, 0, +1, +2}. Из-за этого выбор частной цифры не обязательно должен быть идеальным; более поздние частные цифры могут исправить небольшие ошибки. (Например, пары цифр частного (0, +2) и (1, −2) эквивалентны, поскольку 0 × 4 + 2 = 1 × 4−2.) Этот допуск позволяет выбирать цифры частного, используя только несколько наиболее значимые биты делимого и делителя, вместо того, чтобы требовать вычитания на всю ширину. Это упрощение, в свою очередь, позволяет использовать систему счисления выше 2.
Как и деление без восстановления, заключительными шагами являются заключительное вычитание полной ширины для разрешения последнего бита частного и преобразование частного в стандартную двоичную форму.
В Intel Pentium печально известный процессор ошибка деления с плавающей запятой был вызван неверно закодированной таблицей поиска. Пять из 1066 записей были ошибочно пропущены.[6][7]
Методы быстрого деления
Деление Ньютона – Рафсона
Ньютон – Рафсон использует Метод Ньютона найти взаимный из и умножьте это обратное на найти окончательное частное .
Шаги деления Ньютона – Рафсона:
- Рассчитать смету для взаимного делителя .
- Вычисляйте последовательно более точные оценки обратного. Именно здесь применяется метод Ньютона – Рафсона как таковой.
- Вычислите частное, умножив дивиденд на обратную величину делителя: .
Чтобы применить метод Ньютона, чтобы найти обратную величину , необходимо найти функцию что имеет ноль в . Очевидной такой функцией является , но итерация Ньютона – Рафсона для этого бесполезна, так как ее нельзя вычислить, не зная обратную величину (кроме того, он пытается вычислить точную обратную величину за один шаг, а не допускает итерационных улучшений). Функция, которая действительно работает, - это , для которого итерация Ньютона – Рафсона дает
который может быть рассчитан из используя только умножение и вычитание, или используя два плавленый умножить - складывает.
С точки зрения вычислений выражения и не эквивалентны. Чтобы получить результат с точностью до 2п бит, используя второе выражение, необходимо вычислить произведение между и с удвоенной точностью (п биты).[нужна цитата ] Напротив, продукт между и нужно только вычислить с точностью до п биты, потому что ведущие п биты (после двоичной точки) нули.
Если ошибка определяется как , тогда:
Это возведение ошибки в квадрат на каждом шаге итерации - так называемое квадратичная сходимость метода Ньютона – Рафсона - приводит к тому, что количество правильных цифр в результате примерно удваивается на каждой итерации, свойство, которое становится чрезвычайно ценным, когда задействованные числа содержат много цифр (например, в области больших целых чисел). Но это также означает, что первоначальная сходимость метода может быть сравнительно медленной, особенно если первоначальная оценка плохо выбран.
Для подзадачи выбора начальной оценки , удобно применить битовый сдвиг к делителю D масштабировать так, чтобы 0,5 ≤D ≤ 1; применяя тот же битовый сдвиг к числителю N, гарантирует, что частное не изменится. Тогда можно было бы использовать линейный приближение в виде
для инициализации Ньютона – Рафсона. Чтобы минимизировать максимум модуля погрешности этого приближения на интервале , следует использовать
Коэффициенты линейной аппроксимации определяются следующим образом. Абсолютное значение ошибки равно . Минимум максимального абсолютного значения ошибки определяется Теорема Чебышева о равноволновых колебаниях применительно к . Местный минимум происходит когда , который имеет решение . Функция в этом минимуме должна иметь противоположный знак, что и функция в конечных точках, а именно: . Два уравнения с двумя неизвестными имеют единственное решение и , а максимальная ошибка равна . При таком приближении абсолютное значение погрешности начального значения меньше
Можно сгенерировать полиномиальную аппроксимацию степени больше 1, вычислив коэффициенты с помощью Алгоритм Ремеза. Компромисс заключается в том, что для первоначального предположения требуется больше вычислительных циклов, но, надеюсь, в обмен на меньшее количество итераций Ньютона – Рафсона.
Поскольку для этого метода конвергенция в точности квадратично, отсюда следует, что
шагов достаточно, чтобы вычислить значение до бинарные места. Это оценивается в 3 для IEEE. одинарная точность и 4 для обоих двойная точность и двойной расширенный форматы.
Псевдокод
Следующее вычисляет частное от N и D с точностью до п двоичные места:
Выразите D как M × 2е где 1 ≤ M <2 (стандартное представление с плавающей запятой) D ': = D / 2e + 1 // масштабирование от 0,5 до 1, может быть выполнено с помощью битового сдвига / вычитания экспонентыN ': = N / 2e + 1X: = 48/17 - 32/17 × D ' // предварительное вычисление констант с той же точностью, что и Dповторение раз // можно предварительно вычислить на основе фиксированного P Х: = Х + Х × (1 - D '× X)конецвернуть N '× X
Например, для деления с плавающей запятой двойной точности этот метод использует 10 умножений, 9 сложений и 2 сдвига.
Вариант деления Ньютона – Рафсона.
Метод деления Ньютона-Рафсона можно изменить, чтобы он был немного быстрее, следующим образом. После смещения N и D так что D находится в [0.5, 1.0], инициализировать с
Это наилучшее квадратичное соответствие 1 /D и дает абсолютное значение ошибки, меньшее или равное 1/99. Выбрано так, чтобы ошибка была равна масштабированному третьему порядку. Полином Чебышева первого вида. Коэффициенты должны быть предварительно рассчитаны и жестко запрограммированы.
Затем в цикле используйте итерацию, которая кубирует ошибку.
В Y·E срок новый.
Если цикл выполняется до тех пор, пока X не согласуется с 1 /D на его ведущей п бит, то количество итераций будет не более
99, которое нужно возвести в куб, чтобы получить 2п+1. потом
является частным к п биты.
Использование полиномов более высокой степени либо в инициализации, либо в итерации приводит к снижению производительности, поскольку требуемые дополнительные умножения лучше потратить на выполнение большего количества итераций.
Подразделение Гольдшмидта
Подразделение Гольдшмидта[8] (после Роберта Эллиота Гольдшмидта[9]) использует итерационный процесс многократного умножения делимого и делителя на общий множитель. Fя, выбранный так, чтобы делитель сходился к 1. Это приводит к тому, что дивиденд сходится к искомому частному Q:
Шаги для подразделения Goldschmidt:
- Сгенерируйте оценку коэффициента умножения Fя .
- Умножьте дивиденд и делитель на Fя .
- Если делитель достаточно близок к 1, верните делимое, в противном случае перейдите к шагу 1.
Предполагая N/D был масштабирован так, чтобы 0 <D <1, каждый Fя основан на D:
Умножение дивиденда и делителя на коэффициент дает:
После достаточного количества k итераций .
Метод Гольдшмидта используется в AMD Процессоры Athlon и более поздние модели.[10][11] Он также известен как алгоритм Андерсона Эрла Голдшмидта (AEGP) и реализуется различными процессорами IBM.[12][13]
Биномиальная теорема
Метод Гольдшмидта можно использовать с факторами, позволяющими упростить биномиальная теорема. Предположим, что значение N / D было масштабировано сила двух такой, что .Мы выбрали и . Это дает
- .
После шаги , знаменатель можно округлить до с относительная ошибка
что максимально при когда , обеспечивая минимальную точность двоичные цифры.
Методы больших целых чисел
Методы, разработанные для аппаратной реализации, обычно не масштабируются до целых чисел с тысячами или миллионами десятичных цифр; это часто встречается, например, в модульный сокращение криптография. Для этих больших целых чисел более эффективные алгоритмы деления преобразуют задачу, чтобы использовать небольшое количество умножений, которое затем может быть выполнено с использованием асимптотически эффективного алгоритм умножения такой как Алгоритм Карацубы, Умножение Тоома – Кука или Алгоритм Шёнхаге – Штрассена. В результате вычислительная сложность деления имеет тот же порядок (с точностью до мультипликативной константы), что и умножение. Примеры включают сокращение до умножения на Метод Ньютона так как описано выше,[14] а также немного быстрее Редукция Барретта и Редукция Монтгомери алгоритмы.[15][требуется проверка ] Метод Ньютона особенно эффективен в сценариях, где нужно много раз делить на один и тот же делитель, поскольку после начальной инверсии Ньютона для каждого деления требуется только одно (усеченное) умножение.
Деление на константу
Деление на константу D эквивалентно умножению на его взаимный. Поскольку знаменатель постоянен, значит, он обратный (1 /D). Таким образом, можно вычислить значение (1 /D) один раз во время компиляции, а во время выполнения выполните умножение N·(1/D), а не деление N / D. В плавающая точка арифметическое использование (1 /D) представляет небольшую проблему, но в целое число арифметическая обратная величина всегда будет равна нулю (при условии |D| > 1).
Специально использовать (1 /D); любое значение (Икс/Y), который сводится к (1 /D) может быть использовано. Например, для деления на 3 можно использовать множители 1/3, 2/6, 3/9 или 194/582. Следовательно, если Y если бы была степень двойки, шаг деления уменьшился бы до быстрого сдвига правого бита. Эффект от расчета N/D в качестве (N·Икс)/Y заменяет деление на умножение и сдвиг. Обратите внимание, что круглые скобки важны, так как N·(Икс/Y) будет равен нулю.
Однако если D сам по себе является степенью двойки, нет Икс и Y который удовлетворяет указанным выше условиям. К счастью, (N·Икс)/Y дает точно такой же результат, как N/D в целочисленной арифметике, даже если (Икс/Y) не совсем равно 1 /D, но «достаточно близко», чтобы ошибка, вносимая приближением, была в битах, которые отбрасываются операцией сдвига.[16][17][18]
Как бетон арифметика с фиксированной точкой Например, для 32-битных целых чисел без знака деление на 3 можно заменить умножением на 2863311531/233, умножение на 2863311531 (шестнадцатеричный 0xAAAAAAAB) с последующим сдвигом на 33 бита вправо. Значение 2863311531 рассчитывается как 233/3, затем округлили.
Точно так же деление на 10 может быть выражено как умножение на 3435973837 (0xCCCCCCCD) с последующим делением на 2.35 (или сдвиг вправо на 35 бит).
В некоторых случаях деление на константу можно выполнить за еще меньшее время, преобразовав «умножить на константу» в серия сдвигов и сложений или вычитаний.[19] Особый интерес представляет деление на 10, для которого получается точное частное с остатком, если требуется.[20]
Ошибка округления
![]() | Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Сентябрь 2012 г.) |
Ошибка округления могут быть введены операциями подразделения из-за ограниченного точность.
Смотрите также
Рекомендации
- ^ "Полное руководство по высшей математике по делению в столбик и его вариантам - для целых чисел". Математическое хранилище. 2019-02-24. Получено 2019-06-24.
- ^ Моррис, Джеймс Э .; Иневски, Кшиштоф (22.11.2017). Справочник по применению наноэлектронных устройств. CRC Press. ISBN 978-1-351-83197-0.
- ^ Флинн. «Stanford EE486 (Advanced Computer Arithmetic Division) - раздаточный материал по главе 5 (подразделение)» (PDF). Стэндфордский Университет.
- ^ Харрис, Дэвид Л .; Оберман, Стюарт Ф .; Горовиц, Марк А. (9 сентября 1998 г.). Подразделение SRT: архитектуры, модели и реализации (PDF) (Технический отчет). Стэндфордский Университет.
- ^ Макканн, Марк; Пиппенгер, Николас (2005). «Алгоритмы разделения СТО как динамические системы». SIAM Журнал по вычислениям. 34 (6): 1279–1301. CiteSeerX 10.1.1.72.6993. Дои:10.1137 / S009753970444106X.
- ^ «Статистический анализ дефекта с плавающей точкой». Корпорация Intel. 1994 г.. Получено 22 октября 2013.
- ^ Оберман, Стюарт Ф .; Флинн, Майкл Дж. (Июль 1995 г.). Анализ алгоритмов и реализаций деления (PDF) (Технический отчет). Стэндфордский Университет. CSL-TR-95-675.
- ^ Гольдшмидт, Роберт Э. (1964). Применения деления по сходимости (PDF) (Тезис). M.Sc. диссертация. M.I.T. OCLC 34136725.
- ^ https://web.archive.org/web/20180718114413/https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5392026
- ^ Оберман, Стюарт Ф. (1999). «Алгоритмы деления с плавающей запятой и извлечения квадратного корня и их реализация в микропроцессоре AMD-K7» (PDF). Материалы симпозиума IEEE по компьютерной арифметике: 106–115. Дои:10.1109 / ARITH.1999.762835. S2CID 12793819.
- ^ Содерквист, Питер; Лизер, Мириам (июль – август 1997 г.). «Деление и квадратный корень: выбор правильной реализации». IEEE Micro. 17 (4): 56–66. Дои:10.1109/40.612224.
- ^ С. Ф. Андерсон, Дж. Г. Эрл, Р. Э. Гольдшмидт, Д. М. Пауэрс. IBM 360/370 model 91: исполнительный модуль с плавающей запятой, Журнал исследований и разработок IBM, Январь 1997 г.
- ^ Гай Эвен, Питер-М. Зайдель, Уоррен Э. Фергюсон. Параметрический анализ ошибок алгоритма деления Гольдшмидта. 2004, [1]
- ^ Хассельстрём, Карл (2003). Быстрое деление больших целых чисел: сравнение алгоритмов (PDF) (Докторская диссертация по информатике). Королевский технологический институт. Архивировано из оригинал (PDF) 8 июля 2017 г.. Получено 2017-07-08.
- ^ Барретт, Пол (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.
- ^ Мёллер, Нильс; Гранлунд, Торбьорн (февраль 2011 г.). «Улучшенное деление на инвариантные целые числа» (PDF). Транзакции IEEE на компьютерах. 60 (2): 165–175. Дои:10.1109 / TC.2010.143. S2CID 13347152.
- ^ смешная_рыба.«Труд разделения (Эпизод III): Более быстрое беззнаковое разделение константами».2011.
- ^ LaBudde, Robert A .; Головченко Николай; Ньютон, Джеймс; и Паркер, Дэвид; Massmind: "Бинарное деление на константу"
- ^ Гласные, Р. А. (1992). «Деление на 10». Австралийский компьютерный журнал. 24 (3): 81–85.
дальнейшее чтение
- Уоррен-младший, Генри С. (2013). Хакерское наслаждение (2-е изд.). Эддисон Уэсли - Pearson Education, Inc. ISBN 978-0-321-84268-8.
- Савард, Джон Дж. Г. (2018) [2006]. «Продвинутые арифметические методы». квадиблок. В архиве из оригинала 2018-07-03. Получено 2018-07-16.