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

Эта статья об элементарном рукописном делении. Математическое определение и свойства см. в разделах Деление (математика) и Евклидово деление . Программные алгоритмы см. в разделе Алгоритм деления . Чтобы узнать о других значениях, см. Длинное деление (значения) .

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

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

История

Соответствующие алгоритмы существуют с 12 века. Аль-Самавал аль-Магриби (1125–1174) выполнял вычисления с десятичными числами, которые по сути требуют деления в столбики, что приводило к бесконечным десятичным результатам, но без формализации алгоритма. Кальдрини (1491 г.) является самым ранним печатным примером деления в столбик, известного Данда . в средневековой Италии как метод и это стало более практичным с введением Питискусом ( 1608 г.) десятичной записи дробей. Конкретный алгоритм, используемый в настоящее время, был представлен Генри Бриггсом ок. 1600.

Образование

Недорогие калькуляторы и компьютеры стали наиболее распространенным способом решения задач деления, устраняя традиционные математические упражнения и уменьшая образовательные возможности показать, как это делать с помощью бумаги и карандаша. (Внутренне эти устройства используют один из множества алгоритмов деления , более быстрый из которых основан на приближениях и умножениях для решения задач.) В Соединенных Штатах деление в длину было специально нацелено на то, чтобы уменьшить значение или даже исключить его из школьной программы реформировать математику , хотя традиционно ее вводили в 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 и вычитается из 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. Мы могли бы расширить дивиденд, записав его, скажем, как 500 000... и продолжить процесс (используя десятичную точку в частном непосредственно над десятичной точкой в ​​делимом), чтобы получить десятичный ответ, как в следующем примере: пример.

      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. В конце концов, остаток r прибавляется к растущему частному как дробь : r ⁄ n .

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

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

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

Это позволяет нам поддерживать инвариантное соотношение на каждом этапе: q × m + r = n , где q — частично построенное частное (над скобкой) и r - частично построенный остаток (нижнее число под разделительной скобкой). Обратите внимание, что изначально q=0 и r=n , поэтому это свойство изначально сохраняется; процесс уменьшает r и увеличивает q с каждым шагом, в конечном итоге останавливаемся, когда r<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 < 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

Смешанный режим длинного деления

Для недесятичных валют (таких как британская система £SD до 1971 года) и мер (таких как avoirdupois ) смешанный режим необходимо использовать деления. Рассмотрим разделение 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.

    6359|17    
   −51  |374
    125 |
   −119 |
      69|
     −68|
       1|

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

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

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

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

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

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

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

Алгоритм для произвольной базы

См. Также: Алгоритм деления § Длинное деление

Каждое натуральное число $n$ может быть однозначно представлено в произвольной системе счисления $b>1$ как последовательность цифр ​ $n=\alpha _{0}\alpha _{1}\alpha _{2}...\alpha _{k-1}$ где $0\leq \alpha _{i}<b$ для всех $0\leq i<k$, где $k$ это количество цифр в $n$. Стоимость $n$ по цифрам и основанию

$n=\sum _{i=0}^{k-1}\alpha _{i}b^{k-i-1}$

Позволять $n$ быть дивидендом и $m$ быть делителем, где $l$ это количество цифр в $m$. Если $k<l$, то частное $q=0$ и остаток $r=n$. В противном случае мы выполняем итерацию от $0\leq i\leq k-l$, прежде чем остановиться.

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

$q_{-1}=0$

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

первый $l-1$ цифры $n$.

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

$d_{i}=br_{i-1}+\alpha _{i+l-1}$

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

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

Существует только один такой $\beta _{i}$ такой, что $0\leq r_{i}<m$.

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

По определению остатка $r_{i}$,

$0\leq r_{i}<m$

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

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

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

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

Всегда существует самый большой такой $\beta _{i}$, потому что $0\leq \beta _{i}<b$ и если $\beta _{i}=0$, затем

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

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

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

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

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

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

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

Примеры

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

$0\leq i\leq k-l$	$\alpha _{i+l-1}$	$d_{i}=br_{i-1}+\alpha _{i+l-1}$	$\beta _{i}$	$r_{i}=d_{i}-m\beta _{i}$	$q_{i}=bq_{i-1}+\beta _{i}$
0	2	$10\cdot 1+2=12$	0	$12-37\cdot 0=12$	$10\cdot 0+0=0$
1	6	$10\cdot 12+6=126$	3	$126-37\cdot 3=15$	$10\cdot 0+3=3$
2	0	$10\cdot 15+0=150$	4	$150-37\cdot 4=2$	$10\cdot 3+4=34$
3	2	$10\cdot 2+2=22$	0	$22-37\cdot 0=22$	$10\cdot 34+0=340$
4	5	$10\cdot 22+5=225$	6	$225-37\cdot 6=3$	$10\cdot 340+6=3406$
5	7	$10\cdot 3+7=37$	1	$37-37\cdot 1=0$	$10\cdot 3406+1=34061$

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

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

$0\leq i\leq k-l$	$\alpha _{i+l-1}$	$d_{i}=br_{i-1}+\alpha _{i+l-1}$	$\beta _{i}$	$r_{i}=d_{i}-m\beta _{i}$	$q_{i}=bq_{i-1}+\beta _{i}$
0	4	$10\cdot {\text{f}}+4={\text{f4}}$	${\text{d}}$	${\text{f4}}-12\cdot {\text{d}}={\text{a}}$	$10\cdot 0+{\text{d}}={\text{d}}$
1	1	$10\cdot {\text{a}}+1={\text{a1}}$	8	${\text{a1}}-12\cdot 8=11$	$10\cdot {\text{d}}+8={\text{d8}}$
2	2	$10\cdot 11+2=112$	${\text{f}}$	$112-12\cdot {\text{f}}=4$	$10\cdot {\text{d8}}+{\text{f}}={\text{d8f}}$
3	${\text{d}}=13$	$10\cdot 4+{\text{d}}={\text{4d}}$	4	${\text{4d}}-12\cdot 4=5$	$10\cdot {\text{d8f}}+4={\text{d8f4}}$
4	${\text{f}}=15$	$10\cdot 5+{\text{f}}={\text{5f}}$	5	${\text{5f}}-12\cdot 5=5$	$10\cdot {\text{d8f4}}+5={\text{d8f45}}$

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

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

$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}$

и

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

с $b=16$. Начальные значения $q_{-1}=0$ и $r_{-1}=15$.

$0\leq i\leq k-l$	$\alpha _{i+l-1}$	$d_{i}=br_{i-1}+\alpha _{i+l-1}$	$\beta _{i}$	$r_{i}=d_{i}-m\beta _{i}$	$q_{i}=bq_{i-1}+\beta _{i}$
0	4	$16\cdot 15+4=244$	$13={\text{d}}$	$244-18\cdot 13=10$	$16\cdot 0+13=13$
1	1	$16\cdot 10+1=161$	8	$161-18\cdot 8=17$	$16\cdot 13+8$
2	2	$16\cdot 17+2=274$	$15={\text{f}}$	$274-18\cdot 15=4$	$16\cdot (16\cdot 13+8)+15=16^{2}\cdot 13+16\cdot 8+15$
3	${\text{d}}=13$	$16\cdot 4+13=77$	4	$77-18\cdot 4=5$	$16\cdot (16^{2}\cdot 13+16\cdot 8+15)+4=16^{3}\cdot 13+16^{2}\cdot 8+16\cdot 15+4$
4	${\text{f}}=15$	$16\cdot 5+15=95$	5	$95-18\cdot 5=5$	$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$

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

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

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

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

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

Двоичное деление

Основные статьи: Алгоритм деления § Целочисленное деление (без знака) с остатком и Двоичное число § Деление.

Производительность

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

Обобщения

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

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

Полиномы

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

См. также

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

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

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