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

Стандартный алгоритм деления многозначных чисел

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

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

История

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

Образование

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

Метод

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

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

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

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

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

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

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

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

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

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

Это позволяет нам поддерживать инвариантное соотношение на каждом шаге: 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

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

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

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

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

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

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

 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.

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

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

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

 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-х годов в некоторых учебниках был принят немецкий метод, поскольку он сохраняет порядок между делителем и делимым. ^[12]

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

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

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

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

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

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

Примеры

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

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

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

Таким образом, и . ${\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 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 р. 5 12) ф412дф еа а1 90 112 10е 4д 48 5ф 5а 5

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

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

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

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

На каждой итерации наиболее трудоемкой задачей является выбор . Мы знаем, что существуют возможные значения, поэтому можем найти их с помощью сравнения . Каждое сравнение потребует оценки . Пусть – количество цифр делимого, а – количество цифр делителя . Количество цифр в . Таким образом, умножение равно , а также вычитание . Таким образом, необходимо выбрать . Остальная часть алгоритма - это сложение и сдвиг цифр и на одну цифру влево, поэтому требуется время и в базе , поэтому каждая итерация занимает , или просто . Для всех цифр алгоритм требует времени или по основанию . ${\displaystyle \beta _{i}}$ ${\displaystyle b}$ ${\displaystyle \beta _{i}}$ ${\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-l+1)(l\log(b)+k))}$ ${\displaystyle O(kl\log(b)+k^{2})}$ ${\displaystyle b}$

Обобщения

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

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

Полиномы

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

Смотрите также

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

Рекомендации

1. Вайсштейн, Эрик В. «Длинный дивизион». Математический мир .
2. «Что такое метод фрагментации?». Учебная улица . Проверено 22 марта 2024 г.
3. «Исламская математика». new.math.uiuc.edu . Проверено 31 марта 2016 г.
4. Виктор Дж. Кац, История математики: введение, Аддисон-Уэсли, 2008 г.
5. Уилл Виндзор и Джордж Букер (2005). «Исторический анализ концепции разделения» (PDF) .
6. Генри Бриггс - Оксфордский справочник.
7. Кляйн, Милгрэм. «Роль длинного разделения в учебной программе K-12» (PDF) . CiteSeer . Проверено 21 июня 2019 г.
8. Николсон, В. Кейт (2012), Введение в абстрактную алгебру, 4-е изд., Джон Уайли и сыновья, с. 206.
9. «Символ длинного деления», Wolfram MathWorld , получено 11 февраля 2016 г..
10. Миллер, Джефф (2010), «Символы операции», Самое раннее использование различных математических символов.
11. Хилл, Джон (1772) [Впервые опубликовано в 1712 году], Арифметика как в теории, так и на практике (11-е изд.), Лондон: Straben et al., p. 200 , получено 12 февраля 2016 г.
12. Икяхеймо, Ханнеле: Jakolaskuun ymmärrystä ( на финском языке )

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

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