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

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

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

Хотя связанные алгоритмы существуют с 12 века нашей эры, конкретный алгоритм в современном использовании был введен Генри Бриггсом c.1600 г. н.э.

• 1 Образование
• 2 Метод
  • 2.1 Основная процедура деления n ÷ m в столбик
  • 2.2 Инвариантность и корректность
  • 2.3 Пример с многозначным делителем
  • 2.4 Смешанный режим длинного деления
  • 2.5 Интерпретация десятичных результатов
• 3 Нотация в неанглоязычных странах
  • 3,1 Латинская Америка
  • 3,2 Евразия
• 4 Алгоритм для произвольной базы
  • 4.1 Примеры
  • 4.2 Рациональные коэффициенты
  • 4.3 Двоичное деление
  • 4.4 Производительность
• 5 Обобщения
  • 5.1 Рациональные числа
  • 5.2 Полиномы
• 6 См. Также
• 7 ссылки
• 8 Внешние ссылки

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

В англоязычных странах при длинном делении не используются символы косой черты ⟨ ∕ ⟩ или знака деления ⟨÷, а вместо этого строится таблица. Делитель отделен от дивидендов по правой скобке ⟨ ) ⟩ или вертикальной чертой ⟨ | ⟩; дивиденд отделен от частного по винкулуму (т.е. черты ). Комбинация этих двух символов иногда называется символом длинного деления или скобкой деления. Он развился в 18 веке из более ранней однострочной записи, отделяющей дивиденд от частного левой скобкой.

Процесс начинается с деления крайней левой цифры делимого на делитель. Частное (округленное до целого числа) становится первой цифрой результата, а остаток вычисляется (этот шаг обозначается как вычитание). Этот остаток переносится вперед, когда процесс повторяется для следующей цифры делимого (обозначается как «уменьшение» следующей цифры до остатка). Когда все цифры обработаны и не осталось остатков, процесс завершен.

Пример показан ниже, представляющий деление 500 на 4 (с результатом 125).

  125  (Explanations) 4)500 4  ( 4 × 1 = 4) 10  ( 5 - 4 = 1) 8  ( 4 × 2 = 8) 20  (10 - 8 = 2) 20  ( 4 × 5 = 20) 0  (20 - 20 = 0)

Более подробная разбивка шагов выглядит следующим образом:

1. Найдите кратчайшую последовательность цифр, начиная с левого конца делимого, 500, в которую входит делитель 4 хотя бы один раз. В данном случае это просто первая цифра, 5. Наибольшее число, на которое можно умножить делитель 4, не превышая 5, равно 1, поэтому цифра 1 ставится над 5, чтобы начать построение частного.
2. Затем 1 умножается на делитель 4, чтобы получить наибольшее целое число, кратное делителю 4, не превышая 5 (в данном случае 4). Затем это 4 помещается под и вычитается из 5, чтобы получить остаток 1, который помещается под 4 под 5.
3. После этого первая, еще не использованная цифра в делимом, в данном случае первая цифра 0 после 5, копируется непосредственно под собой и рядом с остатком 1, чтобы сформировать число 10.
4. На этом этапе процесс повторяется достаточно раз, чтобы достичь точки остановки: наибольшее число, на которое можно умножить делитель 4, не превышая 10, равно 2, поэтому 2 написано выше как вторая крайняя левая цифра частного. Затем это 2 умножается на делитель 4, чтобы получить 8, которое является наибольшим кратным 4, но не превышает 10; поэтому 8 записывается под 10, и выполняется вычитание 10 минус 8, чтобы получить остаток 2, который помещается под 8.
5. Следующая цифра делимого (последний 0 из 500) копируется непосредственно под собой и рядом с остатком 2, чтобы получить 20. Затем помещается наибольшее число, на которое можно умножить делитель 4, не превышая 20, то есть 5. выше как третья крайняя левая цифра частного. Это 5 умножается на делитель 4, чтобы получить 20, которое записано ниже, и вычитается из существующих 20, чтобы получить остаток 0, который затем записывается под вторыми 20.
6. На этом этапе, поскольку больше нет цифр, которые можно вывести из делимого, а последний результат вычитания был 0, мы можем быть уверены, что процесс завершен.

Если бы последний остаток, когда у нас закончились цифры дивидендов, был чем-то иным, чем 0, было бы два возможных варианта действий:

1. Мы могли бы просто остановиться на этом и сказать, что делимое на делитель - это частное, записанное вверху, а остаток - внизу, и записать ответ как частное, за которым следует дробь, которая представляет собой остаток, деленный на делитель.
2. Мы могли бы увеличить дивиденд, записав его, скажем, как 500000... и продолжить процесс (используя десятичную точку в частном непосредственно над десятичной точкой в ​​делимом), чтобы получить десятичный ответ, как показано ниже пример.

  31.75 4)127.00 12   (12 ÷ 4 = 3) 07  (0 remainder, bring down next figure) 4  (7 ÷ 4 = 1 r 3) 3.0  (bring down 0 and the decimal point) 2.8  (7 × 4 = 28, 30 ÷ 4 = 7 r 2) 20  (an additional zero is brought down) 20  (5 × 4 = 20) 0

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

Этот пример также показывает, что в начале процесса шаг, который дает ноль, может быть опущен. Поскольку первая цифра 1 меньше делителя 4, первый шаг вместо этого выполняется для первых двух цифр 12. Точно так же, если бы делитель был равен 13, можно было бы выполнить первый шаг на 127, а не на 12 или 1.

Основная процедура деления n ÷ m в столбик

1. Найдите расположение всех десятичных знаков в делимом n и делителе m.
2. При необходимости упростите задачу о длинном делении, переместив десятичные дроби делителя и делимого на одинаковое количество десятичных знаков вправо (или влево) так, чтобы десятичная дробь делителя находилась справа от последней цифры..
3. При делении в столбик держите числа выровненными сверху вниз под таблицей.
4. После каждого шага убедитесь, что остаток от этого шага меньше делителя. Если это не так, есть три возможных проблемы: неправильное умножение, неправильное вычитание или требуется большее частное.
5. В конце концов, остаток, г, добавляют к растущей фактор в качестве фракции,  г / м.

Инвариантность и корректность

Базовое представление шагов процесса (см. Выше) сосредоточено на том, какие шаги должны быть выполнены, а не на свойствах тех шагов, которые гарантируют, что результат будет правильным (в частности, что q × m + r = n, где q - конечное частное, а r - окончательный остаток). Небольшое изменение представления требует большего количества записей и требует, чтобы мы изменили, а не просто обновили цифры частного, но могут пролить больше света на то, почему эти шаги на самом деле дают правильный ответ, позволяя оценивать q × m + r на промежуточном этапе. указывает в процессе. Это иллюстрирует ключевое свойство, используемое при выводе алгоритма (ниже).

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

Это позволяет нам поддерживать инвариантное отношение на каждом шаге: q × m + r = n, где q - частично построенное частное (над скобкой деления), а r - частично построенный остаток (нижнее число под скобкой деления). Обратите внимание, что изначально q = 0 и r = n, поэтому это свойство изначально выполняется; процесс уменьшает r и увеличивает q с каждым шагом, в конечном итоге останавливаясь, когда r lt;m, если мы ищем ответ в форме частное + целочисленный остаток.

Возвращаясь к приведенному выше примеру 500 ÷ 4, мы находим

  125  (q, changes from 000 to 100 to 120 to 125 as per notes below) 4)500 400  ( 4 × 100 = 400) 100  (500 - 400 = 100; now q=100, r=100; note q×4+r = 500.) 80  ( 4 × 20 = 80) 20  (100 - 80 = 20; now q=120, r= 20; note q×4+r = 500.) 20  ( 4 × 5 = 20) 0  ( 20 - 20 = 0; now q=125, r= 0; note q×4+r = 500.)

Пример с многозначным делителем

Можно использовать делитель любого количества цифр. В этом примере 1260257 нужно разделить на 37. Сначала проблема ставится следующим образом:

     37)1260257

Цифры числа 1260257 используются до тех пор, пока не появится число больше или равное 37. Итак, 1 и 12 меньше 37, но 126 больше. Затем вычисляется наибольшее кратное 37, меньшее или равное 126. Итак, 3 × 37 = 111 lt;126, но 4 × 37gt; 126. Кратное 111 написано под 126, а 3 написано вверху, где появится решение:

   3  37)1260257 111

Внимательно обратите внимание, в какой столбец разрядов записаны эти цифры. Число 3 в частном находится в том же столбце (разряды десятков тысяч), что и 6 в дивиденде 1260257, который находится в том же столбце, что и последняя цифра числа 111.

Затем 111 вычитается из строки выше, игнорируя все цифры справа:

   3  37)1260257 111 15

Теперь цифра из следующего меньшего значения делимого копируется и добавляется к результату 15:

   3  37)1260257 111 150

Процесс повторяется: вычитается наибольшее кратное 37, меньшее или равное 150. Это 148 = 4 × 37, поэтому 4 добавляется сверху как следующая цифра частного. Затем результат вычитания расширяется на другую цифру, взятую из делимого:

   34  37)1260257 111 150 148 22

Наибольшее кратное 37, меньшее или равное 22, равно 0 × 37 = 0. Вычитание 0 из 22 дает 22, мы часто не записываем шаг вычитания. Вместо этого мы просто берем еще одну цифру из делимого:

   340 37)1260257 111 150 148 225

Процесс повторяется до тех пор, пока 37 точно не разделит последнюю строку:

   34061 37)1260257 111 150 148 225 222 37

Смешанный режим с длинным делением

Для недесятичных валют (таких как британская система фунтов стерлингов до 1971 года) и мер (таких как экирдупойс ) необходимо использовать смешанный режим деления. Рассмотрим разделение 50 миль 600 ярдов на 37 частей:

   mi -  yd - ft - in  1 - 634  1  9 r. 15" 37) 50 - 600 - 0 - 0 37 22880  66 348 13 23480  66 348 1760 222  37 333 22880  128  29  15 =====  111  348  == 170 === 148 22 66 ==

Каждый из четырех столбцов обрабатывается по очереди. Начиная с миль: 50/37 = 1 остаток 13. Дальнейшее деление невозможно, поэтому выполните длинное умножение на 1760, чтобы преобразовать мили в ярды, в результате получится 22 880 ярдов. Перенесите это в верхнюю часть столбца ярдов и добавьте его к 600 ярдам в дивиденде, получив 23 480. Деление в длину 23 480/37 теперь происходит как обычно, давая 634 с остатком 22. Остаток умножается на 3, чтобы получить футы и переноситься к столбцу футов. Деление стопы в длину дает 1 остаток 29, который затем умножается на двенадцать, чтобы получить 348 дюймов. Деление в длину продолжается, и в строке результата отображается последний остаток в 15 дюймов.

Интерпретация десятичных результатов

Когда частное не является целым числом и процесс деления выходит за пределы десятичной точки, может произойти одно из двух:

1. Процесс может завершиться, что означает достижение остатка 0; или
2. Может быть достигнут остаток, который идентичен предыдущему остатку, который произошел после записи десятичных знаков. В последнем случае продолжать процесс было бы бессмысленно, потому что с этого момента одна и та же последовательность цифр будет появляться в частном снова и снова. Таким образом, над повторяющейся последовательностью рисуется полоса, чтобы указать, что она повторяется бесконечно (т. Е. Каждое рациональное число является либо завершающим, либо повторяющимся десятичным числом ).

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

Латинская Америка

В Латинской Америке (кроме Аргентины, Боливии, Мексики, Колумбии, Парагвая, Венесуэлы, Уругвая и Бразилии ) расчет почти такой же, но записывается иначе, как показано ниже, с теми же двумя примерами, использованными выше. Обычно частное пишется под чертой под делителем. Справа от расчетов иногда проводят длинную вертикальную линию.

  500 ÷ 4 = 125 (Explanations) 4    ( 4 × 1 = 4) 10    ( 5 - 4 = 1) 8    ( 4 × 2 = 8) 20    (10 - 8 = 2) 20    ( 4 × 5 = 20) 0    (20 - 20 = 0)

а также

  127 ÷ 4 = 31.75 124 30  (bring down 0; decimal to quotient) 28  (7 × 4 = 28) 20  (an additional zero is added) 20  (5 × 4 = 20) 0

В Мексике используется англоязычная мировая нотация, за исключением того, что аннотируется только результат вычитания, а вычисления производятся мысленно, как показано ниже:

  125  (Explanations) 4)500 10  ( 5 - 4 = 1) 20  (10 - 8 = 2) 0  (20 - 20 = 0)

В Боливии, Бразилии, Парагвае, Венесуэле, франкоязычной Канаде, Колумбии и Перу используется европейская нотация (см. Ниже), за исключением того, что частное не разделяется вертикальной линией, как показано ниже:

 127|4  −124 31,75 30 −28 20 −20 0

Та же процедура применяется в Мексике, Уругвае и Аргентине, только результат вычитания аннотируется, а расчет выполняется мысленно.

Евразия

В Испании, Италии, Франции, Португалии, Литве, Румынии, Турции, Греции, Бельгии, Беларуси, Украине и России делитель находится справа от дивиденда и разделен вертикальной чертой. Деление также происходит в столбце, но частное (результат) записывается под разделителем и разделяется горизонтальной линией. Такой же метод используется в Иране, Вьетнаме и Монголии.

 127|4  −124|31,75 30 −28 20 −20 0

На Кипре, а также во Франции длинная вертикальная черта отделяет дивиденд и последующие вычитания от частного и делителя, как в приведенном ниже примере 6359, деленного на 17, что составляет 374 с остатком 1.

6

3

5

17

1

374

6

Десятичные числа не делятся напрямую, делимое и делитель умножаются на степень десяти, так что деление включает два целых числа. Следовательно, если бы можно было разделить 12,7 на 0,4 (вместо десятичных знаков использовались запятые), то делимое и делитель сначала изменились бы на 127 и 4, а затем деление продолжилось бы, как указано выше.

В Австрии, Германии и Швейцарии используется форма записи нормального уравнения. lt;dividendgt;: lt;divisorgt; = lt;quotientgt;, с двоеточием ":", обозначающим двоичный инфиксный символ для оператора деления (аналог "/" или "÷"). В этих областях десятичный разделитель записывается в виде запятой. (см. первый раздел о странах Латинской Америки выше, где это делается практически так же):

 127 : 4 = 31,75 −12 07 −4 30 −28 20 −20 0

Такое же обозначение принято в Дании, Норвегии, Болгарии, Северной Македонии, Польше, Хорватии, Словении, Венгрии, Чехии, Словакии, Вьетнаме и в Сербии.

В Нидерландах используются следующие обозначения:

 12 / 135 \ 11,25 12 15 12 30 24 60 60 0

Каждое натуральное число может быть однозначно представлена в произвольной системе счисления в виде последовательности из цифр, где для всех, где есть число цифр в. Значение в виде цифр и основания равно ${\ displaystyle n}$ ${\ displaystyle bgt; 1}$ ${\ Displaystyle п = \ альфа _ {0} \ альфа _ {1} \ альфа _ {2}... \ альфа _ {к-1}}$${\ Displaystyle 0 \ Leq \ альфа _ {я} lt;б}$${\ Displaystyle 0 \ Leq я lt;к}$${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle n}$

${\ Displaystyle п = \ сумма _ {я = 0} ^ {к-1} \ альфа _ {я} Ь ^ {ки-1}}$

Позвольте быть делимым и быть делителем, где - количество цифр в. Если, то и. В противном случае мы выполняем итерацию от до остановки. ${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle l}$${\ displaystyle m}$${\ Displaystyle к lt;л}$${\ displaystyle q = 0}$${\ Displaystyle г = п}$${\ Displaystyle 0 \ Leq я \ Leq kl}$

Для каждой итерации пусть будет частное, извлеченное на данный момент, промежуточное делимое, промежуточный остаток, следующая цифра исходного делимого и следующая цифра частного. По определению цифр в базе,. По определению остатка. Все значения - натуральные числа. Мы инициируем ${\ displaystyle i}$${\ displaystyle q_ {i}}$${\ displaystyle d_ {i}}$${\ displaystyle r_ {i}}$${\ displaystyle \ alpha _ {я}}$${\ displaystyle \ beta _ {я}}$${\ displaystyle b}$${\ Displaystyle 0 \ Leq \ beta _ {я} lt;б}$${\ Displaystyle 0 \ leq r_ {я} lt;м}$

${\ displaystyle q _ {- 1} = 0}$

${\ Displaystyle г _ {- 1} = \ сумма _ {я = 0} ^ {l-2} \ alpha _ {i} b ^ {l-2-i}}$

первые цифры. ${\ displaystyle l-1}$${\ displaystyle n}$

На каждой итерации выполняются три уравнения:

${\ Displaystyle d_ {я} = br_ {я-1} + \ альфа _ {я + l-1}}$

${\ displaystyle r_ {i} = d_ {i} -m \ beta _ {i} = br_ {i-1} + \ alpha _ {i + l-1} -m \ beta _ {i}}$

${\ displaystyle q_ {i} = bq_ {i-1} + \ beta _ {i}}$

Есть только один такой, что. ${\ displaystyle \ beta _ {я}}$${\ Displaystyle 0 \ leq r_ {я} lt;м}$

Согласно определению остатка, ${\ displaystyle r_ {i}}$

${\ Displaystyle 0 \ leq r_ {я} lt;м}$

${\ displaystyle 0 \ leq br_ {я-1} + \ альфа _ {я + l-1} -m \ beta _ {я} lt;м}$

${\ Displaystyle м \ бета _ {я} \ leq br_ {я-1} + \ альфа _ {я + l-1} lt;м (\ бета _ {я} +1)}$

Для левой части неравенства выберем наибольший такой, что ${\ displaystyle \ beta _ {я}}$

${\ Displaystyle м \ бета _ {я} \ leq br_ {я-1} + \ альфа _ {я + l-1}}$

Всегда найдется самый крупный такой, потому что а если, то ${\ displaystyle \ beta _ {я}}$${\ Displaystyle 0 \ Leq \ beta _ {я} lt;б}$${\ displaystyle \ beta _ {я} = 0}$

${\ displaystyle 0 \ leq br_ {я-1} + \ альфа _ {я + l-1}}$

а потому, что,,, это всегда верно. Для правой части неравенства мы предполагаем, что существует наименьшее такое, что ${\ displaystyle bgt; 1}$${\ displaystyle r_ {i-1} \ geq 0}$${\ Displaystyle \ альфа _ {я + l-1} \ geq 0}$${\ displaystyle \ beta _ {я} ^ {\ prime}}$

${\ Displaystyle br_ {я-1} + \ альфа _ {я + l-1} lt;м (\ бета _ {я} ^ {\ prime} +1)}$

Поскольку это наименьшее значение, из которого выполняется неравенство, это должно означать, что для${\ displaystyle \ beta _ {я} ^ {\ prime}}$${\ displaystyle \ beta _ {я} ^ {\ prime} -1}$

${\ Displaystyle br_ {я-1} + \ альфа _ {я + l-1} \ geq м \ бета _ {я} ^ {\ prime}}$

что в точности совпадает с левой частью неравенства. Таким образом,. Как всегда будет существовать, так и будет равно, и существует только одно уникальное, действительное для неравенства. Таким образом, мы доказали существование и уникальность. ${\ Displaystyle \ бета _ {я} = \ бета _ {я} ^ {\ прайм}}$${\ displaystyle \ beta _ {я}}$${\ displaystyle \ beta _ {я} ^ {\ prime}}$${\ displaystyle \ beta _ {я}}$${\ displaystyle \ beta _ {я}}$${\ displaystyle \ beta _ {я}}$

Окончательное частное, а окончательный остаток -${\ displaystyle q = q_ {kl}}$${\ displaystyle r = r_ {kl}}$

Примеры

В базе 10, используя приведенный выше пример с и, начальные значения и. ${\ displaystyle n = 1260257}$${\ displaystyle m = 37}$${\ displaystyle q _ {- 1} = 0}$${\ displaystyle r _ {- 1} = 1}$

${\ Displaystyle 0 \ Leq я \ Leq kl}$	${\ Displaystyle \ альфа _ {я + l-1}}$	${\ Displaystyle d_ {я} = br_ {я-1} + \ альфа _ {я + l-1}}$	${\ displaystyle \ beta _ {я}}$	${\ displaystyle r_ {i} = d_ {i} -m \ beta _ {i}}$	${\ displaystyle q_ {i} = bq_ {i-1} + \ beta _ {i}}$
0	2	${\ Displaystyle 10 \ cdot 1 + 2 = 12}$	0	${\ Displaystyle 12–37 \ cdot 0 = 12}$	${\ Displaystyle 10 \ cdot 0 + 0 = 0}$
1	6	${\ Displaystyle 10 \ cdot 12 + 6 = 126}$	3	${\ displaystyle 126–37 \ cdot 3 = 15}$	${\ Displaystyle 10 \ cdot 0 + 3 = 3}$
2	0	${\ Displaystyle 10 \ cdot 15 + 0 = 150}$	4	${\ displaystyle 150–37 \ cdot 4 = 2}$	${\ Displaystyle 10 \ cdot 3 + 4 = 34}$
3	2	${\ Displaystyle 10 \ cdot 2 + 2 = 22}$	0	${\ displaystyle 22–37 \ cdot 0 = 22}$	${\ displaystyle 10 \ cdot 34 + 0 = 340}$
4	5	${\ Displaystyle 10 \ cdot 22 + 5 = 225}$	6	${\ displaystyle 225–37 \ cdot 6 = 3}$	${\ displaystyle 10 \ cdot 340 + 6 = 3406}$
5	7	${\ Displaystyle 10 \ cdot 3 + 7 = 37}$	1	${\ displaystyle 37–37 \ cdot 1 = 0}$	${\ displaystyle 10 \ cdot 3406 + 1 = 34061}$

Таким образом, и. ${\ displaystyle q = 34061}$${\ displaystyle r = 0}$

В базе 16, с и, начальные значения - и. ${\ displaystyle n = {\ text {f412df}}}$${\ displaystyle m = 12}$${\ displaystyle q _ {- 1} = 0}$${\ displaystyle r _ {- 1} = {\ text {f}}}$

${\ Displaystyle 0 \ Leq я \ Leq kl}$	${\ Displaystyle \ альфа _ {я + l-1}}$	${\ Displaystyle d_ {я} = br_ {я-1} + \ альфа _ {я + l-1}}$	${\ displaystyle \ beta _ {я}}$	${\ displaystyle r_ {i} = d_ {i} -m \ beta _ {i}}$	${\ displaystyle q_ {i} = bq_ {i-1} + \ beta _ {i}}$
0	4	${\ displaystyle 10 \ cdot {\ text {f}} + 4 = {\ text {f4}}}$	${\ displaystyle {\ text {d}}}$	${\ displaystyle {\ text {f4}} - 12 \ cdot {\ text {d}} = {\ text {a}}}$	${\ displaystyle 10 \ cdot 0 + {\ text {d}} = {\ text {d}}}$
1	1	${\ displaystyle 10 \ cdot {\ text {a}} + 1 = {\ text {a1}}}$	8	${\ displaystyle {\ text {a1}} - 12 \ cdot 8 = 11}$	${\ displaystyle 10 \ cdot {\ text {d}} + 8 = {\ text {d8}}}$
2	2	${\ Displaystyle 10 \ cdot 11 + 2 = 112}$	${\ displaystyle {\ text {f}}}$	${\ displaystyle 112-12 \ cdot {\ text {f}} = 4}$	${\ displaystyle 10 \ cdot {\ text {d8}} + {\ text {f}} = {\ text {d8f}}}$
3	${\ displaystyle {\ text {d}} = 13}$	${\ displaystyle 10 \ cdot 4 + {\ text {d}} = {\ text {4d}}}$	4	${\ displaystyle {\ text {4d}} - 12 \ cdot 4 = 5}$	${\ displaystyle 10 \ cdot {\ text {d8f}} + 4 = {\ text {d8f4}}}$
4	${\ displaystyle {\ text {f}} = 15}$	${\ displaystyle 10 \ cdot 5 + {\ text {f}} = {\ text {5f}}}$	5	${\ displaystyle {\ text {5f}} - 12 \ cdot 5 = 5}$	${\ displaystyle 10 \ cdot {\ text {d8f4}} + 5 = {\ text {d8f45}}}$

Таким образом, и. ${\ displaystyle q = {\ text {d8f45}}}$${\ displaystyle r = {\ text {5}}}$

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

${\ displaystyle n = {\ text {f412df}} _ {16} = 15 \ cdot 16 ^ {5} +4 \ cdot 16 ^ {4} +1 \ cdot 16 ^ {3} +2 \ cdot 16 ^ { 2} +13 \ cdot 16 ^ {1} +15 \ cdot 16 ^ {0}}$

а также

${\ displaystyle m = {\ text {12}} _ {16} = 1 \ cdot 16 ^ {1} +2 \ cdot 16 ^ {0} = 18}$

с. Начальные значения - и. ${\ displaystyle b = 16}$${\ displaystyle q _ {- 1} = 0}$${\ displaystyle r _ {- 1} = 15}$

${\ Displaystyle 0 \ Leq я \ Leq kl}$	${\ Displaystyle \ альфа _ {я + l-1}}$	${\ Displaystyle d_ {я} = br_ {я-1} + \ альфа _ {я + l-1}}$	${\ displaystyle \ beta _ {я}}$	${\ displaystyle r_ {i} = d_ {i} -m \ beta _ {i}}$	${\ displaystyle q_ {i} = bq_ {i-1} + \ beta _ {i}}$
0	4	${\ Displaystyle 16 \ cdot 15 + 4 = 244}$	${\ displaystyle 13 = {\ text {d}}}$	${\ displaystyle 244-18 \ cdot 13 = 10}$	${\ Displaystyle 16 \ cdot 0 + 13 = 13}$
1	1	${\ Displaystyle 16 \ cdot 10 + 1 = 161}$	8	${\ displaystyle 161-18 \ cdot 8 = 17}$	${\ Displaystyle 16 \ cdot 13 + 8}$
2	2	${\ Displaystyle 16 \ cdot 17 + 2 = 274}$	${\ displaystyle 15 = {\ text {f}}}$	${\ displaystyle 274-18 \ cdot 15 = 4}$	${\ Displaystyle 16 \ cdot (16 \ cdot 13 + 8) + 15 = 16 ^ {2} \ cdot 13 + 16 \ cdot 8 + 15}$
3	${\ displaystyle {\ text {d}} = 13}$	${\ Displaystyle 16 \ cdot 4 + 13 = 77}$	4	${\ Displaystyle 77-18 \ cdot 4 = 5}$	${\ displaystyle 16 \ cdot (16 ^ {2} \ cdot 13 + 16 \ cdot 8 + 15) + 4 = 16 ^ {3} \ cdot 13 + 16 ^ {2} \ cdot 8 + 16 \ cdot 15 + 4 }$
4	${\ displaystyle {\ text {f}} = 15}$	${\ Displaystyle 16 \ cdot 5 + 15 = 95}$	5	${\ displaystyle 95-18 \ cdot 5 = 5}$	${\ displaystyle 16 \ cdot (16 ^ {3} \ cdot 13 + 16 ^ {2} \ cdot 8 + 16 \ cdot 15 + 4 = 16 ^ {4} \ cdot 13 + 16 ^ {3} \ cdot 8+ 16 ^ {2} \ cdot 15 + 16 ^ {1} \ cdot 4 + 5}$

Таким образом, и. ${\ displaystyle q = 16 ^ {4} \ cdot 13 + 16 ^ {3} \ cdot 8 + 16 ^ {2} \ cdot 15 + 16 ^ {1} \ cdot 4 + 5 = {\ text {d8f45}} _ {16}}$${\ displaystyle r = 5 = {\ text {5}} _ {16}}$

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

   d8f45 r. 5 12) f412df ea a1 90 112 10e 4d 48 5f 5a 5

Рациональные коэффициенты

Если частное не ограничивается целым числом, алгоритм не завершается на. Вместо этого, если тогда по определению. Если остаток равен нулю на любой итерации, то частное представляет собой -адическую дробь и представляется в виде конечного десятичного разложения в базовой позиционной записи. В противном случае это по-прежнему рациональное число, но не -адическое рациональное число, а вместо этого представляется как бесконечное повторяющееся десятичное разложение в базовой позиционной записи. ${\ displaystyle igt; kl}$${\ displaystyle igt; kl}$${\ Displaystyle \ альфа _ {я} = 0}$${\ displaystyle r_ {i}}$ ${\ displaystyle b}$ ${\ displaystyle b}$ ${\ displaystyle b}$ ${\ displaystyle b}$

Бинарное деление

Вычисления в двоичной системе счисления проще, потому что каждая цифра в курсе может быть только 1 или 0 - умножение не требуется, так как умножение на либо приводит к тому же числу, либо к нулю.

Если бы это было на компьютере, умножение на 10 можно было бы представить битовым сдвигом 1 влево, и поиск сводился к логической операции, где истина = 1 и ложь = 0. На каждой итерации выполняются следующие операции.: ${\ displaystyle \ beta _ {я}}$ ${\ displaystyle d_ {i} \ geq m}$${\ Displaystyle 0 \ Leq я \ Leq kl}$

${\ displaystyle {\ begin {align} \ alpha _ {i + l-1} \ amp; {\ mathtt {=}} \ n \ {\ mathtt {\ amp;}} \ (1 \ {\ mathtt {lt;lt;} } \ (k + 1-il)) \\ d_ {i} \ amp; {\ mathtt {=}} \ r_ {i-1} \ {\ mathtt {lt;lt;}} \ 1+ \ alpha _ {i + l-1} \\\ beta _ {i} \ amp; {\ mathtt {=}} \ {\ mathtt {!}} (d_ {i} lt;m) \\ r_ {i} \ amp; {\ mathtt {= }} \ d_ {i} -m \ {\ mathtt {\ amp;}} \ \ beta _ {I} \\ q_ {i} \ amp; {\ mathtt {=}} \ q_ {i-1} \ {\ mathtt {lt;lt;}} \ 1+ \ beta _ {I} \ end {align}}}$

Например, с и начальными значениями являются и. ${\ displaystyle n = 10111001}$${\ displaystyle m = 1101}$${\ displaystyle q _ {- 1} = 0}$${\ displaystyle r _ {- 1} = 101}$

${\ Displaystyle 0 \ Leq я \ Leq kl}$	${\ displaystyle \ alpha _ {я + l-1} \ {\ mathtt {=}} \ n \ {\ mathtt {\ amp;}} \ (1 \ {\ mathtt {lt;lt;}} \ (k + 1- il))}$	${\ Displaystyle d_ {я} \ {\ mathtt {=}} \ r_ {i-1} \ {\ mathtt {lt;lt;}} \ 1+ \ alpha _ {я + l-1}}$	${\ Displaystyle \ бета _ {я} \ {\ mathtt {=}} \! (d_ {я} lt;м)}$	${\ displaystyle r_ {i} \ {\ mathtt {=}} \ d_ {i} -m \ {\ mathtt {\ amp;}} \ \ beta _ {i}}$	${\ displaystyle q_ {i} \ {\ mathtt {=}} \ q_ {i-1} \ {\ mathtt {lt;lt;}} \ 1+ \ beta _ {i}}$
0	1	1011	0	1011 - 0 = 1011	0
1	1	10111	1	10111–1101 = 1010	1
10	0	10100	1	10100 - 1101 = 111	11
11	0	1110	1	1110 - 1101 = 1	111
100	1	11	0	11-0 = 11	1110

Таким образом, и. ${\ displaystyle q = 1110}$${\ displaystyle r = 11}$

Представление

На каждой итерации наиболее трудоемкой задачей является выбор. Мы знаем, что существуют возможные значения, поэтому можем найти их, используя сравнения. Каждое сравнение потребует оценки. Позвольте быть количеством цифр в делимом и быть количеством цифр в делителе. Количество цифр в. Умножение поэтому, также и вычитание. Таким образом, нужно выбрать. Оставшаяся часть алгоритма сложение и цифра-смещение и к левой одной цифре, и так занимает много времени и в базе, так что каждая итерация принимает, или просто. Для всех цифр алгоритм занимает время или в базе. ${\ displaystyle \ beta _ {я}}$${\ displaystyle b}$${\ displaystyle \ beta _ {я}}$ ${\ Displaystyle О (\ журнал (b))}$ ${\ displaystyle d_ {i} -m \ beta _ {i}}$${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle l}$${\ displaystyle m}$${\ displaystyle d_ {i} \ leq l + 1}$${\ displaystyle m \ beta _ {i}}$${\ Displaystyle О (л)}$${\ displaystyle d_ {i} -m \ beta _ {i}}$${\ Displaystyle О (л \ журнал (b))}$${\ displaystyle \ beta _ {я}}$${\ displaystyle q_ {i}}$${\ displaystyle r_ {i}}$${\ Displaystyle О (к)}$${\ Displaystyle О (л)}$${\ displaystyle b}$${\ Displaystyle О (л \ журнал (Ь) + к + л)}$${\ Displaystyle О (л \ журнал (Ь) + к)}$${\ displaystyle k-l + 1}$${\ Displaystyle О ((к-1) (л \ журнал (Ь) + к))}$${\ Displaystyle О (kl \ log (b) + k ^ {2})}$${\ displaystyle b}$

Рациональное число

Деление целых чисел в длину можно легко расширить, включив в него нецелые дивиденды, если они рациональны. Это потому, что каждое рациональное число имеет повторяющееся десятичное расширение. Процедура также может быть расширена для включения делителей, которые имеют конечное или завершающее десятичное расширение (то есть десятичные дроби ). В этом случае процедура включает в себя умножение делителя и делимого на соответствующую степень десяти, чтобы новый делитель был целым числом, используя тот факт, что a  ÷  b = ( ca) ÷ ( cb), а затем действуйте, как указано выше.

Полиномы

Обобщенная версия этого метода, называемая полиномиальным делением в столбик, также используется для деления полиномов (иногда с использованием сокращенной версии, называемой синтетическим делением ).

• Алгоризм
• Арифметика произвольной точности
• Египетское умножение и деление
• Элементарная арифметика
• Деление Фурье
• Полиномиальное деление в столбик
• Алгоритм сдвига корня n-й степени - для нахождения квадратного корня или любого корня n-й степени числа
• Короткое деление

• Алгоритм длинного деления
• Длинное деление и лемма Евклида