산술(arithmetic)에서, 긴 나눗셈(long division)은 손으로 수행하기에 충분히 간단한 여러-자릿수 숫자를 나누는 것에 적합한 표준 나눗셈 알고리듬(division algorithm)입니다. 그것은 나눗셈(division) 문제를 일련의 더 쉬운 단계로 분리합니다.
모든 나눗셈 문제에서 처럼, 피제수(dividend)라고 불리는 한 숫자는 제수(divisor)라고 불리는 또 다른 숫자로 나뉘며, 몫(quotient)이라고 불리는 결과를 생성합니다. 그것은 일련의 간단한 단계를 따름으로써 임의적으로 큰 숫자를 포함하는 계산을 수행하도록 활성화합니다. 긴 나눗셈의 축약된 형식은 짧은 나눗셈(short division)이라고 불리며, 이것은 제수가 오직 한 자릿수를 가질 때 거의 항상 긴 나눗셈 대신 사용됩니다. 덩어리짓기(Chunking) (역시 부분 몫 방법 또는 행맨 방법(hanman method)이라고 불림)은 나눗셈 과정에 대한 보다 전체론적 이해에 기여하는 영국에서 눈에 띄는 덜 기계적인 형식의 긴 나눗셈입니다.
관련된 알고리듬이 기원후 12세기 이후로 존재해 왔지만, 현대에서 사용되는 특정 알고리듬은 기원후 c. 1600년에 헨리 브릭스(Henry Briggs)에 의해 도입되었습니다.
Place in education
비싸지-않은 계산기와 컴퓨터는 나눗셈 문제를 해결하기 위한 가장 공통적인 방법이 되어 왔으며, 전통적인 수학적 연습(mathematical exercise)을 없애고, 종이와 연필 기술로 그렇게 하는 방법을 보여주기 위해 교육 기회를 줄였습니다. (내부적으로, 그들 장치는 다양한 나눗셈 알고리듬(division algorithm) 중 하나를 사용하며, 그 중 빠른 알고리듬은 임무를 달성하기 위해 근사와 곱셈에 의존합니다). 미국에서, 긴 나눗셈은, 비록 전통적으로 4학년 또는 5학년에 도입되었지만, 수학 개혁(reform mathematics)에 의해, 학교 커리큘럼에서 덜 강조하거나, 심지어 제거되는 것을 목표로 삼아 왔습니다.
Method
영어권 국가에서, 긴 나눗셈은 나눗셈 슬래시(division slash) ⟨∕⟩ 또는 나눗셈 기호(division sign) ⟨÷⟩ 상징을 사용하지 않지만 대신 테이블을 구성합니다. 제수(divisor)는 오른쪽 괄호(right parenthesis) ⟨)⟩ 또는 세로 막대(vertical bar) ⟨|⟩에 의해 피제수와 구분됩니다; 피제수는 괄선(vinculum) (즉, 위쪽-막대(overbar))에 의해 몫(quotient)과 분리됩니다. 이들 두 기호의 조합은 긴 나눗셈 기호(long division symbol) 또는 나눗셈 대괄호(division bracket)로 때때로 알려져 있습니다. 그것은 18세기에 왼쪽 괄호(left parenthesis)에 의해 몫에서 피제수를 분리하는 초기 단일-선 표기법에서 발전했습니다.
그 과정은 피제수의 가장-왼쪽 자릿수를 제수로 나눔으로써 시작됩니다. 몫 (정수로 내림)은 결과의 첫 번째 자릿수가 되고, 나머지(remainder)가 계산됩니다 (이 단계는 빼기로 표기됩니다). 이 나머지는 그 과정이 피제수의 다음 자릿수에서 반복될 때 이월됩니다 (다음 자릿수를 나머지 자릿수로 '내림'으로 표기됩니다). 모든 자릿수가 처리되고 나머지가 남지 않을 때, 과정이 완료됩니다.
예제는 아래에 보이며, 4에 의한 500의 나눗셈을 나타내니다 (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)단계의 더 자세한 분석은 다음과 같습니다:
- 제수 4가 적어도 한번 들어가는 피제수 500의 왼쪽 끝에서 시작하여 가장 짧은 자릿수의 수열을 찾습니다. 이 경우에서, 이것은 단순히 첫 번째 자릿수 5입니다. 제수 4는 5를 넘는 것없는 것에 의해 곱해질 수 있는 가장 큰 숫자가 1이므로, 자릿수 1은 몫을 구성하는 것을 시작하기 위해 5 위에 놓습니다.
- 다음으로, 1은 제수 4에 의해 곱해져서, 5를 넘는 것없이 (이 경우에서 4) 제수 4의 배수인 가장 큰 자연수를 얻는 것입니다. 이 4는 그런-다음 5 아래에 놓고 빼서 나머지 1을 얻으며, 이것은 5 아래에 4 아래에 놓입니다.
- 그 후, 피제수에서 아직 사용되지 않은 첫 번째 자릿수, 이 경우에서 5 뒤의 첫 번째 자릿수 0은 숫자 10을 형성하기 위해 자체 바로 아래 및 나머지 1 다음에 복사됩니다.
- 이 시점에서 그 과정은 중지하는 지점에 도달하기 위해 충분한 횟수를 반복됩니다: 제수 4는 10을 초과하는 것없이 곱해지게 되는 있는 가장 큰 숫자는 2이므로, 2는 두 번째로 가장 왼쪽 몫 자릿수로 쓰입니다. 이 2는 그런-다음 제수 4를 곱해져서 8을 얻으며, 이것은 10을 초과하지 않는 4의 가장 큰 배수입니다; 따라서 8은 10 아래에 쓰이고, 뺄셈 10 빼기 8은 나머지 2를 얻기 위해 수행되며, 이것은 8 아래에 위치됩니다.
- 피제수의 다음 자릿수 (500에서 마지막 0)는 20을 형성하기 위해 자체 바로 아래에 나머지 2 다음에 복사됩니다. 그런-다음 제수 4는 20을 초과하는 것없이 곱해질 수 있는 가장 큰 숫자, 5가 세 번째 가장 왼쪽 몫 자릿수로 위에 위치됩니다. 이 5는 20을 얻기 위해 제수 4에 곱해지며, 이것은 아래에 쓰이고 기존 20에서 나머지 0을 산출하기 위해 빼지며, 이것은 그런-다음 두 번째 20 아래에 쓰입니다.
- 이 시점에서, 더 이상 피제수에서 내릴 수 있는 자릿수가 없고 마지막 뺄셈 결과가 0이었으모, 우리는 과정이 완료되었음을 확신할 수 있습니다.
만약 우리가 피제수 자릿수의 끝에 도달했을 때 마지막 나머지가 0 이외의 어떤 값이면, 두 가지 가능한 결정이 있었을 것입니다:
- 우리는 바로 거기서 멈추고 제수로 나누어진 피제수는 맨 아래에 쓰인 나머지와 함께 맨 위에 쓰인 몫임을 말하고, 그 답을 몫과 나머지를 제수로 나눈 분수로 뒤에 씁니다.
- 우리는, 다음 예제에서 처럼, 십진수 답을 얻기 위해, 말하자면, 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이면, 우리는 12 또는 1이 아닌 127에서 첫 번째 단계를 수행할 것입니다.
Basic procedure for long division of n ÷ m
- 피제수 n과 제수 m에서 모든 십진 점의 위치를 찾으십시오.
- 만약 필요하면, 제수와 피제수의 십진 점을 같은 숫자의 십진 자리만큼, 제수의 십진이 마지막 자릿수의 오른쪽에 오도록, 오른쪽 (또는 왼쪽)으로 이동함으로써 긴 나눗셈 문제를 단순화합니다.
- 긴 나눗셈을 행할 때, 테이블 아래에서 맨 위에서 맨 아래로 숫자를 똑바로 정렬하십시오.
- 각 단계 후에, 해당 단계에 대해 나머지가 제수보다 작은지 확인하십시오. 만약 그렇지 않으면, 세 가지 가능한 문제가 있습니다: 곱셈이 틀렸거나, 뺄셈이 틀렸거나, 더 큰 몫이 요구됩니다.
- 마지막에서, 나머지, r은 증가하는 몫에 분수(fraction), r/m로 더해집니다.
Example with multi-digit divisor
임의의 자릿수의 숫자의 제수가 사용될 수 있습니다. 이 예제에서, 1260257은 37로 나누어집니다. 먼저 문제는 다음과 같이 설정됩니다:
37)1260257
숫자 1260257의 자릿수는 37보다 더 크거나 같은 숫자가 나올 때까지 가져옵니다. 따라서 1과 12는 37보다 작지만, 126은 더 큽니다. 다음으로, 126보다 작거나 같은 37의 최대 배수가 계산됩니다. 따라서 3 × 37 = 111 < 126이지만, 4 × 37 > 126입니다. 배수 111은 126 아래에 쓰이고 3은 해가 나타나게 될 맨 위에 쓰입니다:
3
37)1260257
111
이들 자릿수가 쓰이는 위치-값 열에 면밀하게 주목하십시오. 몫에서 3은 피제수 1260257에서 6과 같은 열 (만-자리)에 놓이며, 이것은 111의 마지막 자릿수와 같은 열입니다.
111은 그런-다음 오른쪽에 있는 모든 자릿수를 무시하고 위 줄에서 빼집니다:
3
37)1260257
111
15
이제 피제수의 다음으로 더 작은 자리 값에서 자릿수가 아래로 복사되고 결과 15에 붙여집니다:
3
37)1260257
111
150
그 과정이 반복됩니다: 150보다 작거나 같은 37의 가장 큰 배수가 빼집니다. 이것은 148 = 4 × 37이므로, 4가 다음 몫 자릿수로 맨 위에 더해집니다. 그런-다음 뺄셈의 결과는 피제수에서 가져온 또 다른 자릿수로 확장됩니다:
34
37)1260257
111
150
148
22
22보다 작거나 같은 37의 최대 배수는 0 × 37 = 0입니다. 22에서 0을 빼면 22를 제공하며, 우리는 종종 뺄셈 단계를 쓰지 않습니다. 대신에, 우리는 피제수에서 또 다른 숫자를 가져옵니다:
340
37)1260257
111
150
148
225
그 과정은 37이 정확하게 마지막 줄을 나눌 때까지 반복됩니다:
34061
37)1260257
111
150
148
225
222
37
Mixed mode long division
(1971년 이전의 영국 £sd 시스템과 같은) 비-십진 통화와 (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입니다. 더 이상 나눗셈이 가능하지 않으므로, 마일을 야드로 변환하는 1,760에 의한 긴 곱셈을 수행하여, 그 결과는 22,880 야드입니다. 이것을 야드 열의 맨 위로 가져가고 그것을 피제수에서 600 야드에 더하여 23,480을 얻습니다. 23,480 / 37의 긴 나눗셈이 이제 표준으로 진행되어 나머지 22를 갖는 634를 산출합니다. 나머지는 피트를 얻기 위해 3에 의해 곱해지고 피트 열까지 가져갑니다. 피트의 긴 나눗셈은 나머지 29를 갖는 1을 제공하며 그런-다음 12를 곱하여 348 인치를 얻습니다. 긴 나눗셈은 결과 줄 위에 보이는 15인치의 마지막 나머지를 가질 때까지 계속됩니다.
Interpretation of decimal results
몫이 정수가 아니고 나눗셈 과정이 십진 점 이상으로 확장될 때, 다음 두 가지 중 하나가 발생할 수 있습니다:
- 그 과정은 종료되며, 이것은 0의 나머지가 도달되었음을 의미합니다; 또는
- 십진 점을 쓴 후 발생한 이전 나머지와 동일한 나머지에 도달할 수 있습니다. 후자의 경우에서, 과정을 계속하는 것은 의미가 없는데, 왜냐하면 해당 지점부터 같은 자릿수의 수열이 계속해서 몫에 나타나기 때문입니다. 따라서 반복되는 수열 위에 막대가 그려서 영원히 반복됨을 나타냅니다 (즉, 모든 각 유리수는 종료되거나 반복 십진수입니다).
Notation in non-English-speaking countries
중국, 일본, 한국은 인도를 포함한 영어권 국가와 같은 표기법을 사용합니다. 다른 곳에서는, 같은 일반적인 원칙이 사용되지만, 그림은 종종 다르게 배열됩니다.
Latin America
라틴 아메리카(Latin America) (아르헨티나(Argentina), 볼리비아(Bolivia), 멕시코(Mexico), 콜롬비아(Colombia), 파라과이(Paraguay), 베네수엘라(Venezuela), 우루과이(Uruguay) 및 브라질[(Brazil) 제외)에서, 그 계산이 거의 정확하게 같지만, 위에서 사용된 같은 두 가지 예제와 함께 아래에서 보이는 것처럼 다르게 내려씁니다. 보통 몫은 제수 아래에 그려진 막대 아래에 쓰입니다. 긴 나눗셈 줄은 때때로 계산의 오른쪽에 그려집니다.
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
멕시코(Mexico)에서, 오직 뺄셈 결과가 주석으로 달려 있고 그 계산이 아래에 보이는 것처럼 암기로 행해지는 점을 제외하고는 영어권 세계 표기법이 사용됩니다:
125 (Explanations)
4)500
10 ( 5 - 4 = 1)
20 (10 - 8 = 2)
0 (20 - 20 = 0)
볼리비아(Bolivia), 브라질(Brazil), 파라과이(Paraguay), 베네수엘라(Venezuela), 퀘벡(Quebec), 콜롬비아(Colombia) 및 페루(Peru)에서, 아래에 보이는 것처럼 그 몫이 수직선에 의해 분리되지 않는 점을 제외하고, 유럽 표기법 (아래 참조)이 사용됩니다:
127|4
−124 31,75
30
−28
20
−20
0
같은 절차가 멕시코(Mexico), 우루과이(Uruguay) 및 아르헨티나(Argentina)에서 적용되며, 오직 뺄셈의 결과가 주석이 달려 있고 계산은 암기로 행해집니다.
Eurasia
스페인, 이탈리아, 프랑스, 포르투갈, 리투아니아, 루마니아, 터키, 그리스, 벨기에, 벨로루시, 우크라이나 및 러시아에서, 제수는 피제수 오른쪽에 있고, 세로 막대로 분리됩니다. 나눗셈은 역시 열에서 발생하지만, 몫 (결과)은 제수 아래에 쓰이고, 가로 줄로 구분됩니다. 같은 방법은 이란과 몽골에서 사용됩니다.
127|4
−124|31,75
30
−28
20
−20
0
키프로스, 마찬가지로 프랑스에서, 아래의 예제, 17에 의한 6359의 나눗셈에서 처럼, 긴 세로 막대가 몫과 제수에서 피제수와 후속 뺄셈을 분리하며, 그 결과는 나머지 1을 갖는 374입니다.
| 6 | 3 | 5 | 9 | 17 |
| − 5 | 1 | 374 | ||
| 1 | 2 | 5 | ||
| − 1 | 1 | 9 | ||
| 6 | 9 | |||
| − | 6 | 8 | ||
| 1 |
십진수는 직접 나누어질 수 없고, 피제수와 제수는 나눗셈이 두 정수를 포함하도록 10의 거듭제곱에 의해 곱해집니다. 그러므로, 만약 우리가 12,7을 0,4로 나누면 (십진 점 대신에 쉼표가 사용됨), 피제수와 제수는 먼저 127과 4로 변경되고, 그런-다음 나눗셈은 위에서 처럼 진행됩니다.
오스트리아(Austria), 독일(Germany) 및 스위스(Switzerland)에서, 정규 방정식의 표기법적 형식이 사용됩니다. <피제수> : <제수> = <몫>, 콜론 ":"은 나눗셈 연산자 ("/" 또는 "÷"와 유사함)에 대해 이진 중위 기호를 나타냅니다. 이 지역에서, 십진 구분기호는 쉼표로 쓰입니다. (비교. 위의 라틴 아메리카 국가의 첫 번째 섹션, 여기서 그것은 같은 방법으로 수직적으로 행해집니다):
127 : 4 = 31,75
−12
07
−4
30
−28
20
−20
0
같은 표기법은 덴마크(Denmark), 노르웨이(Norway), 불가리아(Bulgaria), 북 마케도니아(North Macedonia), 폴란드(Poland), 크로아티아(Croatia), 슬로베니아(Slovenia), 헝가리(Hungary), 체코 공화국(Czech Republic), 슬로바키아(Slovakia), 베트남(Vietnam) 및 세르비아(Serbia)에서 채택됩니다.
네덜란드(Netherlands)에서, 다음 표기법이 사용됩니다:
12 / 135 \ 11,25
12
15
12
30
24
60
60
0
Algorithm for arbitrary base
모든 각 자연수(natural number) \(\displaystyle n\)은 임의의 숫자 밑수(number base) \(\displaystyle b>1\)에서 자릿수(digits)의 수열(sequence) \(\displaystyle n=\alpha_{0}\alpha_{1}\alpha_{2}...\alpha_{k-1}\)로 고유하게 표현될 수 있으며, 여기서 모든 \(\displaystyle 0\leq i<k\)에 대해 \(\displaystyle 0\leq\alpha_{i}<b\)이고 \(\displaystyle k\)는 \(\displaystyle n\)에서 자릿수의 숫자입니다. 그것의 자릿수와 밑수에 관한 \(\displaystyle n\)의 값은 다음입니다:
\(\quad\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\)로부터 반복합니다.
각 반복(iteration) \(\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 n\)의 처음 \(\displaystyle l-1\) 자릿수와 함께 다음으로 시작합니다:
\(\quad\displaystyle q_{-1}=0\)
\(\quad\displaystyle r_{-1}=\sum_{i=0}^{l-2}\alpha_{i}b^{k-i-1}\).
모든 각 반복과 함께, 세 방정식은 참입니다:
\(\quad\displaystyle d_{i}=br_{i-1}+\alpha_{i+l-1}\)
\(\quad\displaystyle r_{i}=d_{i}-m\beta_{i}=br_{i-1}+\alpha_{i+l-1}-m\beta_{i}\)
\(\quad\displaystyle q_{i}=bq_{i-1}+\beta_{i}\)
\(\displaystyle 0\leq r_{i}<m\)을 만족하는 하나의 그러한 \(\displaystyle \beta_{i}\)가 오직 존재합니다.
\(\displaystyle \beta_{i}\)의 존재와 고유성의 증명
나머지 \(\displaystyle r_{i}\)의 정의에 따라,
\(\quad\displaystyle 0 \leq r_{i} < m\)
\(\quad\displaystyle 0 \leq br_{i-1} + \alpha_{i+l-1} - m \beta_{i} < m\)
\(\quad\displaystyle m \beta_{i} \leq br_{i-1} + \alpha_{i+l-1} < m(\beta_{i}+1)\)
부등식의 왼쪽 변에 대해, 우리는 다음을 만족하는 가장 큰 \(\displaystyle \beta_{i}\)를 선택합니다:
\(\quad\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\)이면, 다음이기 때문입니다:
\(\quad\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}\)가 있음을 가정합니다:
\(\quad\displaystyle br_{i-1} + \alpha_{i+l-1} < m(\beta_{i}^{\prime} + 1)\)
이것은 부등식이 참이 유지되는 가장 작은 \(\displaystyle \beta_{i}^{\prime}\)이므로, 이것은 \(\displaystyle \beta_{i}^{\prime}-1\)에 대해 다음임을 반드시 의미합니다:
\(\quad\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}\)의 존재와 고유성을 입증했습니다.\(\square\)
최종 몫은 \(\displaystyle q = q_{k-l}\)이고 최종 나머지는 \(\displaystyle r = r_{k-l}\)입니다.
Examples
밑수 10(base 10)에서, \(\displaystyle n = 1260257\)과 \(\displaystyle m = 37\)을 갖는 위의 예제를 사용하여, 초기 값은 \(\displaystyle q_{-1} = 0\)이고 \(\displaystyle r_{-1} = 1\)입니다.
따라서, \(\displaystyle q = 34061\)이고 \(\displaystyle r = 0\)입니다.
밑수 16(base 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에 대해 덧셈(addition), 뺄셈, 또는 곱셈 테이블(multiplication table)을 가지지 않으면, 이 알고리듬은 만약 숫자가 십진수(decimal)로 변환되고 끝에서 밑수 b로 다시 변환되면 여전히 작동합니다. 예를 들어, 위의 예제와 함께,
\(\quad\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\)
및
\(\quad\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 r. 5
12 ) f412df
ea
a1
90
112
10e
4d
48
5f
5a
5
Rational quotients
만약 몫이 정수가 되도록 구속되지 않으면, 알고리듬은 \(\displaystyle i>k-l\)에 대해 종료되지 않습니다. 대신에, 만약 \(\displaystyle i>k-l\)이면, 정의에 의해 \(\displaystyle \alpha_{i}=0\)입니다. 만약 나머지 \(\displaystyle r_{i}\)가 임의의 반복에서 영과 같으면, 몫은 \(\displaystyle b\)-진수 분수이고, 밑수 \(\displaystyle b\) 위치 표기법에서 유한 십진(finite decimal) 전개로 표현됩니다. 그렇지 않으면, 그것은 여전히 유리수(rational number)지만 \(\displaystyle b\)-진수 유리수는 아니고, 대신에 밑수 \(\displaystyle b\) 위치 표기법에서 무한 반복되는 십진(repeating decimal) 전개로 표현됩니다.
Binary division
[[Binary number|이진 숫자 시스템(binary number system)]] 내에서 계산은 더 단순한데, 왜냐하면 과정에서 각 자릿수는 오직 1 또는 0이 될 수 있습니다 – 곱셈은 그것이 [[Identity element|같은 숫자(same number)]] 또는 [[Absorbing element|영(zero)]]영을 초래하므로 곱셈으로 요구되지 않습니다.
만약 이것이 컴퓨터에서 였으면, 10에 의한 곱셈은 왼쪽으로 1의 [[bit shift|비트 시프트(bit shift)]]에 의해 나타낼 수 있고, \(\displaystyle \beta_{i}\)를 찾는 것은 [[logical operation|논리적 연산(logical operation)]] \(\displaystyle d_{i} \geq m\)로 줄어들며, 여기서 참 = 1이고 거짓 = 0입니다. 모든 각 반복 \(\displaystyle 0 \leq i \leq k - l\)과 함께, 다음 연산이 행해집니다:
\(\displaystyle \begin{align}
\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{align}\)
예를 들어, \(\displaystyle n = 10111001\)과 \(\displaystyle m = 1101\)과 함께, 초기 값이 \(\displaystyle q_{-1} = 0\)이고 \(\displaystyle r_{-1} = 101\)입니다.
따라서, \(\displaystyle q = 1110\)이고 \(\displaystyle r = 11\)입니다.
Performance
각 반복에서, 대부분의 시간-소비 임무는 \(\displaystyle \beta_{i}\)를 선택하는 것입니다. 우리는 \(\displaystyle b\) 가능한 값이 있음을 알므로, 우리는 \(\displaystyle O(\log(b))\) 비교를 사용하여 \(\displaystyle \beta_{i}\)를 찾을 수 있습니다. 각 비교는 \(\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 \beta_{i}\)를 선택하기 위해 \(\displaystyle O(l\log(b))\)를 취합니다. 알고리듬의 나머지는 \(\displaystyle q_{i}\)와 한 자릿수 왼쪽으로 \(\displaystyle r_{i}\)의 덧셈과 자릿수-시프팅이고, 따라서 밑수 \(\displaystyle b\)에서 시간 \(\displaystyle O(k)\)와 \(\displaystyle O(l)\)을 취하므로, 각 반복은 \(\displaystyle O(l\log(b) + k + l)\), 또는 단지 \(\displaystyle O(l\log(b) + k)\)를 취합니다. 모든 \(\displaystyle k - l + 1\) 자릿수에 대해, 알고리듬은 밑수 \(\displaystyle b\)에서 시간 \(\displaystyle O((k - 1)(l\log(b) + k))\), 또는 \(\displaystyle O(kl\log(b) + k^2)\)를 취합니다.
Generalizations
Rational numbers
정수의 긴 나눗셈은, 그것들이 유리수(rational)인 한, 비-정수 피제수를 포함하기 위해 쉽게 확장될 수 있습니다. 이것은 모든 각 유리수는 반복되어 발생하는 십진수(recurring decimal) 확장을 가지기 때문입니다. 그 절차는 유한 또는 종료하는 십진(decimal) 확장 (즉, 십진 분수(decimal fraction))를 가지는 제수를 포함하기 위해 역시 확장될 수 있습니다. 이 경우에서 절차는 새로운 제수가 정수가 되도록 십의 적절한 거듭제곱에 의한 제수와 피제수를 곱하고 – a ÷ b = (ca) ÷ (cb)라는 사실의 이점을 취하여 – 그런-다음 위와 같이 진행하는 것을 포함합니다.
Polynomials
다항식 긴 나눗셈(polynomial long division)이라고 불리는 이 방법의 일반화된 버전은 다항식(polynomial)을 나누는 것에 대해 역시 사용됩니다 (때때로 조립 제법(synthetic division)이라고 불리는 속기 버전을 사용합니다).
See also
External links
- Long Division Algorithm
- [1] Long Division and Euclid's Lemma
