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

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

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

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

Место в образовании [ править ]

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

Метод [ править ]

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

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

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

  1 2 5 (Пояснения) 4) 500 4 (4 × 1 = 4) 1 0 (5 - 4 = 1 ) 8 (4 × 2 = 8) 2 0 (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 , вниз следующая цифра) 4 (7 ÷ 4 = 1 r 3)  3.0 (сбить 0 и десятичную точку) 2,8 (7 × 4 = 28, 30 ÷ 4 = 7 r 2) 20 (сбит дополнительный ноль) 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 <m, если мы ищем ответ в форме частное + целочисленный остаток.

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

  1 2 5 ( q , изменяется от 000 до 100 до 1 20 до 1 2 5 в соответствии с примечаниями ниже) 4) 500 400 (4 × 100 = 400) 100 (500 - 400 = 100 ; теперь q = 100 , r = 100 ; обратите внимание, q × 4 + r = 500. ) 80 (4 × 20 = 80) 20 (100 - 80 = 20 ; теперь q = 1 20 , r = 20 ; обратите внимание: q × 4 + r = 500. ) 20 (4 × 5 = 20) 0 (20-20 = 0; теперь q = 1 2 5 , r = 0 ; примечание q × 4 + r = 500. )

Пример с многозначным делителем [ править ]

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

   37) 1260257

Цифры числа 1260257 используются до тех пор, пока не появится число больше или равное 37. Итак, 1 и 12 меньше 37, но 126 больше. Затем вычисляется наибольшее кратное 37, меньшее или равное 126. Итак, 3 × 37 = 111 <126, но 4 × 37> 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 частей:

 ми - ярд - фут - ин  1 - 634 1 9 р. 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. Может быть достигнут остаток, который идентичен предыдущему остатку, который произошел после записи десятичных знаков. В последнем случае продолжать процесс было бы бессмысленно, потому что с этого момента одна и та же последовательность цифр будет появляться в частном снова и снова. Таким образом, над повторяющейся последовательностью рисуется полоса, чтобы указать, что она повторяется бесконечно (т. Е. Каждое рациональное число является либо завершающим, либо повторяющимся десятичным числом ).

Обозначения в неанглоязычных странах [ править ]

В этом разделе есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) В этом разделе не процитировать любые источники . Пожалуйста, помогите улучшить этот раздел , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален . ( Март 2019 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) Этот раздел может потребовать очистки для соответствия стандартам качества Википедии . Конкретная проблема заключается в том, что эти блоки не очень хорошо демонстрируют нотацию - изображения, вероятно, были бы лучше. Кроме того, использование разных чисел в примерах снижает акцент на обозначениях, которые должны отображаться, так что, может быть, унифицировать это? Пожалуйста, помогите улучшить этот раздел, если можете. ( Март 2019 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

Латинская Америка [ править ]

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

 500 ÷ 4 = 1 2 5 (Пояснения) 4 (4 × 1 = 4) 1 0 (5 - 4 = 1 ) 8 (4 × 2 = 8) 2 0 (10-8 = 2 ) 20 (4 × 5 = 20) 0 (20-20 = 0)

и

 127 ÷ 4 = 31,75 124  30 (уменьшить 0; десятичное в частное) 28 (7 × 4 = 28) 20 (добавляется дополнительный ноль) 20 (5 × 4 = 20) 0

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

  1 2 5 (Пояснения) 4) 500 1 0 (5-4 = 1 ) 2 0 (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.

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

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

 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 b> 1}$ ${\ Displaystyle п = \ альфа _ {0} \ альфа _ {1} \ альфа _ {2} ... \ альфа _ {к-1}}$${\ Displaystyle 0 \ Leq \ альфа _ {я} <б}$${\ Displaystyle 0 \ Leq я <к}$${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle n}$

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

Позвольте быть делимым и быть делителем, где - количество цифр в . Если , то и . В противном случае мы выполняем итерацию от до остановки.${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle l}$${\ displaystyle m}$${\ Displaystyle к <л}$${\ 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 _ {я} <б}$${\ Displaystyle 0 \ leq r_ {я} <м}$

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

${\displaystyle r_{-1}=\sum _{i=0}^{l-2}\alpha _{i}b^{l-2-i}}$

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

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

${\displaystyle d_{i}=br_{i-1}+\alpha _{i+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 _{i}}$${\displaystyle 0\leq r_{i}<m}$

Доказательство существования и уникальности${\displaystyle \beta _{i}}$  -

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

${\displaystyle 0\leq r_{i}<m}$

${\displaystyle 0\leq br_{i-1}+\alpha _{i+l-1}-m\beta _{i}<m}$

${\displaystyle m\beta _{i}\leq br_{i-1}+\alpha _{i+l-1}<m(\beta _{i}+1)}$

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

${\displaystyle m\beta _{i}\leq br_{i-1}+\alpha _{i+l-1}}$

Всегда найдется самый крупный такой , потому что а если , то${\displaystyle \beta _{i}}$${\displaystyle 0\leq \beta _{i}<b}$${\displaystyle \beta _{i}=0}$

${\displaystyle 0\leq br_{i-1}+\alpha _{i+l-1}}$

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

${\displaystyle br_{i-1}+\alpha _{i+l-1}<m(\beta _{i}^{\prime }+1)}$

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

${\displaystyle br_{i-1}+\alpha _{i+l-1}\geq m\beta _{i}^{\prime }}$

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

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

Примеры [ править ]

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

${\displaystyle 0\leq i\leq k-l}$	${\displaystyle \alpha _{i+l-1}}$	${\displaystyle d_{i}=br_{i-1}+\alpha _{i+l-1}}$	${\displaystyle \beta _{i}}$	${\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 i\leq k-l}$	${\displaystyle \alpha _{i+l-1}}$	${\displaystyle d_{i}=br_{i-1}+\alpha _{i+l-1}}$	${\displaystyle \beta _{i}}$	${\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 i\leq k-l}$	${\displaystyle \alpha _{i+l-1}}$	${\displaystyle d_{i}=br_{i-1}+\alpha _{i+l-1}}$	${\displaystyle \beta _{i}}$	${\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 еа а1 90 112 10e 4d 48 5f 5а 5

Рациональные коэффициенты [ править ]

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

Двоичное деление [ править ]

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

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

${\displaystyle {\begin{aligned}\alpha _{i+l-1}\ &{\mathtt {=}}\ n\ {\mathtt {\&}}\ (1\ {\mathtt {<<}}\ (k+1-i-l))\\d_{i}\ &{\mathtt {=}}\ r_{i-1}\ {\mathtt {<<}}\ 1+\alpha _{i+l-1}\\\beta _{i}\ &{\mathtt {=}}\ {\mathtt {!}}(d_{i}<m)\\r_{i}\ &{\mathtt {=}}\ d_{i}-m\ {\mathtt {\&}}\ \beta _{I}\\q_{i}\ &{\mathtt {=}}\ q_{i-1}\ {\mathtt {<<}}\ 1+\beta _{I}\end{aligned}}}$

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

${\displaystyle 0\leq i\leq k-l}$	${\displaystyle \alpha _{i+l-1}\ {\mathtt {=}}\ n\ {\mathtt {\&}}\ (1\ {\mathtt {<<}}\ (k+1-i-l))}$	${\displaystyle d_{i}\ {\mathtt {=}}\ r_{i-1}\ {\mathtt {<<}}\ 1+\alpha _{i+l-1}}$	${\displaystyle \beta _{i}\ {\mathtt {=}}\ !(d_{i}<m)}$	${\displaystyle r_{i}\ {\mathtt {=}}\ d_{i}-m\ {\mathtt {\&}}\ \beta _{i}}$	${\displaystyle q_{i}\ {\mathtt {=}}\ q_{i-1}\ {\mathtt {<<}}\ 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 _{i}}$${\displaystyle b}$${\displaystyle \beta _{i}}$ O ( log ⁡ ( b ) ) {\displaystyle O(\log(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 O(l)}$${\displaystyle d_{i}-m\beta _{i}}$${\displaystyle O(l\log(b))}$${\displaystyle \beta _{i}}$${\displaystyle q_{i}}$${\displaystyle r_{i}}$${\displaystyle O(k)}$${\displaystyle O(l)}$${\displaystyle b}$${\displaystyle O(l\log(b)+k+l)}$, или просто . Для всех цифр алгоритм занимает время или в базе .${\displaystyle O(l\log(b)+k)}$${\displaystyle k-l+1}$${\displaystyle O((k-1)(l\log(b)+k))}$${\displaystyle O(kl\log(b)+k^{2})}$${\displaystyle b}$

Обобщения [ править ]

Рациональные числа [ править ]

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

Полиномы [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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