Как найти остаток от деления алгоритм

Алгоритмы вычисления частного и остатка от целочисленного деления

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

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

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

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

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

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

• Q = Частное
• R = Остаток

является выходом.

Содержание

• 1 Деление повторным вычитанием
• 2 Длинное деление
  • 2.1 Целочисленное деление (без знака) с остатком
    • 2.1.1 Пример
• 3 Медленные методы деления
  • 3.1 Восстановление деления
  • 3.2 Невосстанавливающееся деление
  • 3.3 Разделение SRT
• 4 Методы быстрого деления
  • 4.1 Деление Ньютона – Рафсона
    • 4.1.1 Псевдокод
    • 4.1.2 Вариант деления Ньютона – Рафсона
  • 4.2 Деление Гольдшмидта
    • 4.2.1 Биномиальная теорема
• 5 Методы больших целых
• 6 Деление на константу
• 7 Ошибка округления
• 8 См. Также
• 9 Ссылки
• 10 Дополнительная литература
• 11 Внешние ссылки

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

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

пока N ≥ D do N: = N - D end return N

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

функция деления (N, D), если D = 0, то ошибка (DivisionByZero) end, если 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 вернуть div_unsigned (N, D) конец функции div_unsigned (N, D) Q: = 0; R: = N, а R ≥ D do Q: = Q + 1 R: = R - D end return (Q, R) end

Эта процедура всегда дает R ≥ 0. Хотя она очень проста, она требует Ω (Q) шагов, и поэтому он экспоненциально медленнее, чем даже алгоритмы медленного деления, такие как деление в столбик. Это полезно, если известно, что Q невелик (являясь алгоритмом, чувствительным к выводам ), и может служить исполняемой спецификацией.

Длинное деление

Длинное деление — это стандартный алгоритм, используемый для ручного деления многозначных чисел, выраженных в десятичной системе счисления. Он постепенно сдвигается от левого края делимого к правому, вычитая максимально возможное кратное делителя (на уровне цифр) на каждом этапе; тогда кратные становятся цифрами частного, а окончательная разница становится остатком.

При использовании с двоичной системой счисления этот метод формирует основу для (беззнакового) целочисленного деления с алгоритмом остатка ниже. Краткое деление — это сокращенная форма длинного деления, подходящая для однозначных делителей. Разделение на части — также известное как метод частичных частных или метод палача — это менее эффективная форма длинного деления, которую легче понять. Допуская вычитание большего количества кратных, чем то, что есть в настоящее время на каждом этапе, также может быть разработан более свободный вариант длинного деления

Целочисленное деление (без знака) с остатком

Следующий алгоритм, двоичная версия знаменитого деления в столбик разделит N на D, поместив частное в Q, а остаток в R. В следующем коде все значения обрабатываются как целые числа без знака.

если D = 0, то ошибка (DivisionByZeroException) end Q: = 0 - инициализировать частное и остаток до нуля R: = 0 для i: = n - 1.. 0 do - где n - количество битов в NR : = 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(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)

end. Q = 11 2(310) и R = 0.

Методы медленного деления

Все методы медленного деления основаны на стандартном рекуррентном уравнении

R j + 1 = B × R j — qn — (j + 1) × D { displaystyle R_ {j + 1} = B times R_ {j} -q_ {n- (j + 1)} times D ,},

где:

• Rj- j-й частичный остаток от деления
• B — система счисления (основание, обычно 2 внутри компьютеров и калькуляторов)
• qn — (j + 1) — цифра частного в позиции n− (j + 1), где позиции цифр пронумерованы от наименее значимого 0 до наиболее значимого n − 1
• n — количество цифр в частном
• D — делитель

Восстановление деления

Восстановление деления работает с дробными числами с фиксированной точкой и зависит от предположения 0 < D < N.

Цифры частного q формируются из набора цифр {0,1}.

Базовый алгоритм для двоичного (основание 2) восстанавливающего деления:

R: = ND: = 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 перед вычитание в дополнительном регистре T (т. е. T = R << 1) and copying register T to R when the result of the subtraction 2R − D is negative.

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

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

Невосстанавливающее деление использует набор цифр {−1, 1} для частных цифр вместо {0, 1}. Алгоритм более сложен, но имеет Преимущество аппаратной реализации в том, что существует только одно решение и сложение / вычитание на бит частного; нет шага восстановления после вычитания, что потенциально сокращает количество операций почти вдвое и позволяет выполнять их быстрее. Базовый алгоритм для двоичного (основание 2) невосстановительное деление неотрицательных чисел:

R: = ND: = 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, затем q [i] : = +1 R: = 2 * R - D иначе q [i]: = −1 R: = 2 * R + D конец, если конец - Примечание: N = числитель, D = знаменатель, n = # бит, R = Частичный остаток, q (i) = бит #i частного.

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

Преобразование следующего частного в набор цифр {0,1}:
Начало:	Q = 111 1 ¯ 1 1 ¯ 1 1 ¯ { displaystyle Q = 111 { bar {1} } 1 { bar {1}} 1 { bar {1}}}
1. Сформируйте положительный член:	P = 11101010 { displaystyle P = 11101010 ,}
2. Замаскируйте отрицательный член *:	M = 00010101 { displaystyle M = 00010101 ,}
3. Вычтите: P — M { displaystyle PM}:	Q = 11010101 { displaystyle Q = 11010101 ,}
*. (Знаковое двоичное представление с дополнением до единицы без Дополнение до двух )

Если -1 цифра в Q { displaystyle Q}сохранена как обычные нули (0), то P { displaystyle P}isQ { displaystyle Q}и вычисление M { displaystyle M}тривиально: выполнить дополнение до единицы (побитовое дополнение) на исходном Q { displaystyle Q}.

Q: = Q - bit.bnot (Q) * Подходит, если -1 цифра в Q представлена ​​как обычные нули.

Наконец, частные, вычисленные этим алгоритмом, всегда нечетные, а остаток в R находится в диапазоне -D ≤ R < D. For example, 5 / 2 = 3 R −1. To convert to a positive remainder, do a single restoring step after Q is converted from non-standard form to standard form:

, если R < 0 then Q := Q − 1 R := R + D -- Needed only if the Remainder is of interest. end if

Фактический остаток равен R>>n. (Как и в случае восстановления деления, младшие биты R используются с той же скоростью, что и биты частного Q, и обычно для обоих используется один регистр сдвига.)

SRT-разделение

Названо в честь его создателей (Суини, Ro Bertson и Tocher), разделение SRT является популярным методом разделения во многих реализациях микропроцессора. Разделение SRT аналогично разделению без восстановления, но оно использует таблицу поиска на основе делимого и делителя для определения каждой цифры частного.

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

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

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

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

Деление Ньютона-Рафсона

Ньютон-Рафсон использует метод Ньютона, чтобы найти обратное от D { displaystyle D}и умножьте это обратное на N { displaystyle N}, чтобы найти окончательное частное Q { displaystyle Q}.

Шаги деления Ньютона – Рафсона:

1. Вычислить оценку X 0 { displaystyle X_ {0}}для обратного 1 / D { displaystyle 1 / D}делителя D { displaystyle D}.
2. Последовательное вычисление более точных оценок X 1, X 2,…, XS { displaystyle X_ {1}, X_ {2}, ldots, X_ {S}}обратного. Именно здесь применяется метод Ньютона – Рафсона как таковой.
3. Вычислить частное, умножив делимое на обратную величину делителя: Q = NXS { displaystyle Q = NX_ {S}}.

Чтобы применить метод Ньютона, чтобы найти обратную величину D { displaystyle D}, необходимо найти функцию f (X) { displaystyle f (X) }с нулем в X = 1 / D { displaystyle X = 1 / D}. Очевидной такой функцией является f (X) = DX — 1 { displaystyle f (X) = DX-1}, но итерация Ньютона – Рафсона для этого бесполезна, поскольку не может быть вычисляется без знания обратного значения D { displaystyle D}(кроме того, он пытается вычислить точное обратное значение за один шаг, а не допускает итерационных улучшений). Действительно работает функция f (X) = (1 / X) — D { displaystyle f (X) = (1 / X) -D}, для которой функция Ньютона – Рафсона итерация дает

X i + 1 = X i — f (X i) f ′ (X i) = X i — 1 / X i — D — 1 / X i 2 = X i + X i (1 — DX я) знак равно Икс я (2 — DX я), { Displaystyle X_ {я + 1} = X_ {я} — {е (X_ {я}) над f ‘(X_ {i})} = X_ {я } — {1 / X_ {i} -D over -1 / X_ {i} ^ {2}} = X_ {i} + X_ {i} (1-DX_ {i}) = X_ {i} (2 -DX_ {i}),}

который может быть вычислен из X i { displaystyle X_ {i}}, используя только умножение и вычитание, или используя два объединенного умножения– добавляет.

С точки зрения вычислений, выражения X i + 1 = X i + X i (1 — DX i) { displaystyle X_ {i + 1} = X_ {i} + X_ {i } (1-DX_ {i})}и X i + 1 = X i (2 — DX i) { displaystyle X_ {i + 1} = X_ {i} (2- DX_ {i})}не эквивалентны. Чтобы получить результат с точностью 2n битов при использовании второго выражения, нужно вычислить произведение между X i { displaystyle X_ {i}}и (2 — DX i) { displaystyle (2-DX_ {i})}с удвоенной заданной точностью X i { displaystyle X_ {i}}(n бит). Напротив, произведение между X i { displaystyle X_ {i}}и (1 — DX i) { displaystyle (1-DX_ {i})}необходимо вычислять только с точностью до n бит, потому что первые n битов (после двоичной точки) (1 — DX i) { displaystyle (1-DX_ {i})}— нули.

Если ошибка определяется как ε i = 1 — DX i { displaystyle varepsilon _ {i} = 1-DX_ {i}}, то:

ε i + 1 = 1 — DX i + 1 = 1 — D (X i (2 — DX i)) = 1-2 DX i + D 2 X i 2 = (1 — DX i) 2 = ε i 2. { displaystyle { begin {align} 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 {align}}}

Это возведение в квадрат ошибки на каждом шаге итерации — так называемая квадратичная сходимость метода Ньютона – Рафсона — приводит к тому, что количество правильных цифр в результате примерно удваивается для каждой итерации, свойство, которое становится чрезвычайно ценным, когда задействованные числа имеют много цифр (например, в области больших целых чисел). Но это также означает, что начальная сходимость метода может быть сравнительно медленной, особенно если исходная оценка X 0 { displaystyle X_ {0}}выбрана плохо.

Для подзадачи выбора начальной оценки X 0 { displaystyle X_ {0}}удобно применить битовый сдвиг к делителю D, чтобы масштабировать его. так что 0,5 ≤ D ≤ 1; применяя тот же битовый сдвиг к числителю N, можно гарантировать, что частное не изменится. Тогда можно было бы использовать линейное приближение в форме

X 0 = T 1 + T 2 D ≈ 1 D { displaystyle X_ {0} = T_ {1} + T_ {2} D приблизительно { frac {1} {D}} ,}

для инициализации Ньютона – Рафсона. Чтобы минимизировать максимум абсолютного значения ошибки этого приближения на интервале [0,5, 1] ​​{ displaystyle [0,5,1]}, следует использовать

X 0 = 48 17 — 32 17 Д. { displaystyle X_ {0} = {48 over 17} — {32 over 17} D. ,}

Коэффициенты линейной аппроксимации определяются следующим образом. Абсолютное значение ошибки | ε 0 | = | 1 — D (Т 1 + Т 2 D) | { displaystyle | varepsilon _ {0} | = | 1-D (T_ {1} + T_ {2} D) |}. Минимум максимального абсолютного значения погрешности определяется теоремой Чебышева о равноволновых колебаниях, примененной к F (D) = 1 — D (T 1 + T 2 D) { displaystyle F (D) = 1-D (T_ {1} + T_ {2} D)}. Локальный минимум F (D) { displaystyle F (D)}возникает, когда F ′ (D) = 0 { displaystyle F ‘(D) = 0}, у которого есть решение D = — T 1 / (2 T 2) { displaystyle D = -T_ {1} / (2T_ {2})}. Функция в этом минимуме должна иметь знак, противоположный знаку функции в конечных точках, а именно: F (1/2) = F (1) = — F (- T 1 / (2 T 2)) { displaystyle F (1/2) = F (1) = — F (-T_ {1} / (2T_ {2}))}. Два уравнения с двумя неизвестными имеют уникальное решение T 1 = 48/17 { displaystyle T_ {1} = 48/17}и T 2 = — 32/17 { displaystyle T_ {2} = — 32/17}, а максимальная ошибка составляет F (1) = 1/17 { displaystyle F (1) = 1/17}. При использовании этого приближения абсолютное значение ошибки начального значения меньше

| ε 0 | ≤ 1 17 ≈ 0,059. { displaystyle vert varepsilon _ {0} vert leq {1 over 17} приблизительно 0,059. ,}

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

Поскольку для этого метода сходимость точно квадратичная, отсюда следует, что

S = ⌈ log 2 ⁡ P + 1 log 2 ⁡ 17 ⌉ { displaystyle S = left lceil log _ {2} { frac {P + 1} { log _ {2} 17}} right rceil ,}

шагов достаточно, чтобы вычислить значение до P { displaystyle P ,}двоичные разряды. Это оценивается в 3 для IEEE одинарной точности и 4 для форматов двойной точности и двойного расширения.

Псевдокод

Следующее вычисляет частное Nи Dс точностью Pдвоичных разрядов:

Выразите D как M × 2, где 1 ≤ M <2 (стандартное представление с плавающей запятой) D ': = D / 2 // масштабирование от 0,5 до 1, может быть выполнено с помощью битового сдвига / вычитания экспоненты N': = N / 2 X: = 48/17 - 32/17 × D '// предварительно вычисляем константы с той же точностью, что и D repeat⌈ log 2 ⁡ P + 1 log 2 ⁡ 17 ⌉ { displaystyle  left  lceil  log _ {2} { frac {P + 1} { log _ {2} 17}}  right  rceil ,}раз // может быть предварительно вычислено на основе фиксированного PX: = X + X × (1 - D '× X) endreturn N' × X

Например, для числа с плавающей запятой двойной точности деление, этот метод использует 10 умножений, 9 сложений и 2 сдвига.

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

Метод деления Ньютона-Рафсона можно изменить, чтобы он был немного быстрее, следующим образом. После сдвига N и D так, что D находится в [0,5, 1,0], инициализируйте с помощью

X: = 140 33 + D ⋅ (- 64 11 + D ⋅ 256 99). { displaystyle X: = { frac {140} {33}} + D cdot left ({ frac {-64} {11}} + D cdot { frac {256} {99}} right).}

Это наилучшее квадратичное соответствие 1 / D, которое дает абсолютное значение ошибки меньше или равное 1/99. Он выбран так, чтобы ошибка была равна повторно масштабированному полиному Чебышева третьего порядка первого рода. Коэффициенты должны быть предварительно рассчитаны и жестко запрограммированы.

Затем в цикле используйте итерацию, которая кубирует ошибку.

E: = 1 — D ⋅ Икс { displaystyle E: = 1-D cdot X}

Y: = X ⋅ E { displaystyle Y: = X cdot E}

X: = X + Y + Y ⋅ E. { displaystyle X: = X + Y + Y cdot E.}

Термин Y · E является новым.

Если цикл выполняется до тех пор, пока X не согласуется с 1 / D на своих ведущих битах P, то количество итераций будет не более

⌈ log 3 ⁡ (P + 1 log 2 ⁡ 99) ⌉ { displaystyle left lceil log _ {3} left ({ frac {P + 1} { log _ {2} 99}} right) right rceil}

, которое является числом количество умноженных на 99 необходимо кубов, чтобы получить 2. Тогда

Q: = N ⋅ X { displaystyle Q: = N cdot X}

является частным к P битам.

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

Деление Гольдшмидта

В делении Гольдшмидта (по Роберту Эллиотту Гольдшмидту) используется итерационный процесс многократного умножения и делимого, и делителя на общий множитель F i, выбранный таким образом, что делитель сходится к 1. В результате дивиденд сходится к искомому частному Q:

Q = NDF 1 F 1 F 2 F 2 F… F…. { 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, each Fiосновано на D:

F i + 1 = 2 — D я. { displaystyle F_ {i + 1} = 2-D_ {i}.}

Умножение делимого и делителя на множитель дает:

N i + 1 D i + 1 = N i D i F i + 1 Ф я + 1. { displaystyle { frac {N_ {i + 1}} {D_ {i + 1}}} = { frac {N_ {i}} {D_ {i}}} { frac {F_ {i + 1} } {F_ {i + 1}}}.}

После достаточного числа k итераций Q = N k { displaystyle Q = N_ {k}}.

Метод Гольдшмидта используется в AMD процессоры Athlon и более поздние модели. Он также известен как алгоритм Андерсона Эрла Голдшмидта (AEGP) и реализуется различными процессорами IBM.

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

Метод Гольдшмидта можно использовать с факторами, которые позволяют упрощать до биномиальная теорема. Предположим, что N / D было масштабировано с помощью степени двойки, так что D ∈ (1 2, 1] { displaystyle D in ({ tfrac {1} {2}}, 1 ]}. Выбираем D = 1 — x { displaystyle D = 1-x}и F i = 1 + x 2 i { displaystyle F_ {i} = 1 + x ^ {2 ^ {i}}}. Это дает

N 1 — x = N ⋅ (1 + x) 1 — x 2 = N ⋅ (1 + x) ⋅ (1 + x 2) 1 — x 4 = ⋯ = Q ′ = N ′ = N ⋅ (1 + x) ⋅ (1 + x 2) ⋅ ⋅ ⋅ (1 + x 2 (n — 1)) D ′ = 1 — x 2 n ≈ 1 { 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}} приблизительно 1}}}.

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

ε n = Q ′ — N ′ Q ′ = x 2 n { Displaystyle varepsilon _ {n} = { frac {Q’-N ‘} {Q’}} = x ^ {2 ^ {n}}}

, максимальное значение 2–2 n { displaystyle 2 ^ {- 2 ^ {n}}}когда x = 1 2 { displaystyle x = {1 over 2}}, обеспечивая минимальную точность 2 n { displaystyle 2 ^ {n}}двоичные цифры.

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

Методы, разработанные для аппаратной реализации, обычно не масштабируются до целых чисел с тысячами или миллионами десятичных цифр; это часто встречается, например, в модульных сокращениях в криптографии. Для этих больших целых чисел более эффективные алгоритмы деления преобразуют задачу, чтобы использовать небольшое количество умножений, которое затем может быть выполнено с использованием асимптотически эффективного алгоритма умножения, такого как алгоритм Карацубы, Умножение Тоома – Кука или алгоритм Шёнхаге – Штрассена. В результате вычислительная сложность деления имеет тот же порядок (с точностью до константы умножения), что и умножение. Примеры включают сокращение до умножения с помощью метода Ньютона как, описанного выше, а также несколько более быстрые алгоритмы редукции Барретта и уменьшения Монтгомери. Метод Ньютона особенно эффективен в сценариях, где нужно много раз делить на один и тот же делитель, поскольку после начальной инверсии Ньютона для каждого деления требуется только одно (усеченное) умножение.

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

Деление на константу 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, но «достаточно близко», чтобы ошибка, вносимая приближением, была в битах, которые отбрасываются операцией сдвига.

В качестве конкретного примера арифметики с фиксированной точкой для 32-битных целых чисел без знака деление на 3 может быть заменено умножением на 2863311531 / 2, умножение на 2863311531 (шестнадцатеричное 0xAAAAAAAB) с последующим сдвигом на 33 бита вправо. Значение 2863311531 рассчитывается как 2/3, затем округляется в большую сторону.

Подобным образом деление на 10 может быть выражено как умножение на 3435973837 (0xCCCCCCCD) с последующим делением на 2 (или сдвиг на 35 битов вправо).

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

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

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

См. также

Ссылки

Дополнительная литература

• Уоррен-младший, Генри С. (2013). Hacker’s Delight (2-е изд.). Эддисон Уэсли — Pearson Education, Inc. ISBN 978-0-321-84268-8.
• Савард, Джон Дж. Дж. (2018) [ 2006]. «Продвинутые арифметические методы». квадиблок. Архивировано из оригинала 2018-07-03. Проверено 16 июля 2018 г.

Внешние ссылки

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

Онлайн калькулятор деление с остатком

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

Деление с остатком — это когда вы делите одно натуральное число на другое, и получаете остаток, который не равен нулю.

Деление с остатком целых положительных чисел

Это операция, при которой одно целое положительное число (делимое) делится на другое целое положительное число (делитель), и остается некоторое число, которое нельзя разделить на делитель без остатка.

Формула
a=b⋅q+ra = b cdot q + r

Деление с остатком может быть полезно при решении математических задач, например, для определения четности или нечетности числа. Если остаток от деления на 2 равен 0, то число четное, иначе — нечетное.

Пример
При делении 1010 на 33 с остатком получится результат 33 и остаток 11, так как 3⋅3=93 cdot3=9, и оставшаяся единица не может быть разделена на 33.

Деление с остатком целых отрицательных чисел

Деление с остатком для целых отрицательных чисел работает по тем же правилам, что и для целых положительных чисел.

Формула
r=a−b⋅qr = a − b cdot q

Вот простой алгоритм деления с остатком целых отрицательных чисел:

1. Найдите модуль делимого и делителя, то есть возьмите их положительные значения;
2. Разделите модуль делимого на модуль делителя, так же как при обычном делении с остатком;
3. Получите неполное частное и остаток;
4. Если делимое и делитель имеют разные знаки, то прибавьте 1 к неполному частному;
5. Вычислите остаток, используя формулу r=a−b⋅qr = a — b cdot q.

Пример
Если мы делим −7-7 на 33, мы получим неполное частное −2-2 и остаток −1-1. А если мы делим −7-7 на −3-3, то неполное частное будет равно 22, а остаток будет 11.

Деление с остатком положительного числа на целое отрицательное

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

Первым шагом необходимо найти модули делимого и делителя, то есть их значения без учета знака. Затем выполнить обычное деление модуля делимого на модуль делителя и получить неполное частное и остаток. Далее, если знаки делимого и делителя различны, необходимо к неполному частному прибавить 1. Если же знаки одинаковы, то ничего добавлять не нужно. Наконец, вычислить окончательный остаток, используя формулу r=a−b⋅qr = a — b cdot q, где rr — остаток, aa — делимое, bb — делитель, qq — неполное частное.

Пример
Если нужно выполнить деление 2727 на −5-5, то сначала найдем модули: ∣27∣=27|27| = 27 и ∣−5∣=5|-5| = 5. Затем выполним обычное деление: 275=5frac{27}{5} = 5 (остаток 22). Так как знаки чисел различны, добавляем 11 к неполному частному и получаем 66. Наконец, вычисляем окончательный остаток: 27−(−5)⋅6=727 — (-5) cdot 6 = 7. Итак, 27:−5=−627:-5 = -6 (остаток 77).

Деление с остатком отрицательного числа на положительное

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

Пример
Рассмотрим выражение: (−15):4=(−3)(-15) : 4 = (-3) (остаток −3-3). В этом выражении −15-15 — это делимое, 44 — делитель, −3-3 — остаток, а −3-3 — неполное частное. Чтобы проверить правильность ответа, нужно умножить неполное частное (−3)(-3) на делитель (4)(4) и добавить к произведению остаток (−3)(-3). Получим: (−3)⋅4+(−3)=−15(-3) cdot 4 + (-3) = -15. Результат равен делимому, значит, деление с остатком выполнено верно.

Как проверить деление с остатком

Чтобы проверить деление с остатком, необходимо выполнить два шага:
Выполнить деление с остатком, как это делается обычно.
Проверить правильность результата, используя формулу: делимое == делитель ⋅cdot частное ++ остаток.

Формула
a=b⋅c+da = b cdot c + d, где aa — делимое, bb — делитель, cc — неполное частное, dd — остаток.

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

Пример
Задача: 274=6frac{27}{4} = 6 и остаток 33:

• Делимое равно 2727.
• Делитель равен 44.
• Частное равно 66.
• Остаток равен 33.
  Проверяем формулу: 27=4⋅6+327 = 4 cdot 6 + 3. Формула выполняется, поэтому результат верный.