장제법

산술에서 장분할은 손으로 수행할 수 있을 정도로 간단한 다자리 아라비아 숫자(위치 표기법)를 나누기에 적합한 표준분할 알고리즘이다. 그것은 분열 문제를 일련의 더 쉬운 단계로 세분화한다.

모든 분할 문제에서와 같이 배당이라고 하는 한 수를 디비저(divisor)라고 하는 다른 숫자로 나누어 지분이라는 결과를 산출한다. 그것은 일련의 간단한 단계를 따라 임의로 큰 숫자와 관련된 계산을 수행할 수 있게 한다.^[1] 긴 나눗셈의 축약형식을 짧은 나눗셈이라고 하는데, 디비서가 한 자리수만 가질 때 긴 나눗셈 대신 거의 항상 사용된다. 청킹(일부 인용법 또는 행인법이라고도 함)은 영국에서 두드러지는 장기 분할의 덜 기계적인 형태로서 분할 과정에 대한 보다 전체적인 이해에 기여한다.

AD 12세기 이후 관련 알고리즘이 존재해 왔지만,^[2] 현대용에 있어서의 특정 알고리즘은 AD 1600 AD에 의해 도입되었다.^[3]

교육

값싼 계산기와 컴퓨터는 분업 문제를 해결하는 가장 흔한 방법이 되어 전통적인 수학적 연습을 없애고 종이와 연필 기법으로 어떻게 하는지를 보여주는 교육 기회를 줄였다.(내부적으로 그러한 장치들은 다양한 분업 알고리즘 중 하나를 사용하는데, 그중에서 더 빠른 것이 의존한다. 작업 달성을 위한 근사 및 곱셈). 미국에서는 전통적으로 4학년이나 5학년에서 도입되었지만 개혁 수학에 의해 긴 분업화가 특히 탈강증, 또는 심지어 학교 교과과정에서의 탈락의 표적이 되어 왔다.^[4]

방법

영어권 국가에서 긴 분할은 분할 슬래시 ⟨∕ or⟩ 또는 분할 기호 ⟨÷ symbols 기호를 사용하지 않고 대신 tableau를 구성한다.^[5] 배당금은 오른쪽 괄호 ⟨)⟩ 또는 수직 막대 ⟨로 배당금과 분리되며, 배당금은 빈쿨룸(즉, 오버바)의 몫과 분리된다. 이 두 기호의 조합은 긴 분할 기호 또는 분할 괄호로 알려져 있다.^[6] 그것은 18세기에 왼쪽 괄호 안의 몫으로부터 배당금을 분리하는 이전의 단행 표기법으로부터 발전했다.^[7]^[8]

배당금의 가장 왼쪽 자리를 디비저로 나누는 것으로 절차가 시작된다. 지수(정수로 반올림)는 결과의 첫 번째 숫자가 되고, 나머지는 계산된다(이 단계는 뺄셈으로 표기된다). 이 나머지는 다음 숫자의 배당금에 대해 프로세스가 반복될 때(다음 숫자를 나머지 숫자로 '아래로 가져오는' 것으로 통지됨) 이행을 수행한다. 모든 숫자를 처리하고 나머지를 남기지 않으면 프로세스가 완료된다.

500 대 4의 구분을 나타내는 예는 아래와 같다(125의 결과).

  125 (해설) 4) 4) 4)500 (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을 얻는다. 나머지 1은 5 아래의 4 아래에 둔다.
그 후에, 배당금에서 첫 번째 사용되지 않은 자리, 즉 이 경우, 5 다음에 첫 번째 자리 0은 자기 바로 밑에 그리고 나머지 1 옆에 복사되어 숫자 10을 형성한다.
이 시점에서는 프로세스가 정지점에 도달할 만큼 반복된다. 10을 초과하지 않고 4를 곱할 수 있는 가장 큰 숫자는 2이므로, 2는 두 번째 가장 왼쪽의 몫의 숫자로 위에 쓰여 있다. 그 다음 이 2를 분할자 4에 곱하여 8을 얻는다. 이는 10을 초과하지 않는 4의 가장 큰 배수량이다. 따라서 8을 10 이하로 쓰고, 나머지 2를 얻기 위해 감산 10 빼기 8을 행한다. 나머지 2는 8보다 아래에 위치한다.
배당금의 다음 자리(마지막 0 in 500)는 자기 바로 아래, 나머지 2 옆에 복사하여 20을 형성한다. 그 다음 20을 초과하지 않고 4를 곱할 수 있는 가장 큰 숫자인 5를 세 번째 가장 왼쪽의 몫의 숫자로 위에 놓는다. 이 5에 20을 곱하면 20이 되는데, 이 값은 아래에 쓰여지고 나머지 0을 산출하기 위해 기존 20에서 빼면 두 번째 20보다 아래에 기록된다.
이때 배당에서 더 이상 내려올 자리가 없고 마지막 뺄셈 결과가 0이었기 때문에 그 과정이 끝났다고 장담할 수 있다.

만약 배당률이 바닥난 마지막 남은 시간이 0이 아니었다면, 두 가지 행동 방침이 있었을 것이다.

우리는 거기서 그만하고, 배당금을 배당금으로 나눈 것이 상부에 쓰여진 몫이고, 나머지 몫은 분배자로 나눈 몫이라고 하고, 그 뒤에 나머지 몫은 분배자로 나눈 몫으로 답을 쓰면 된다.
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 r 2) 20 (추가 0은 아래로 가져오기) 20 (0은 아래로 가져오기) 20 (0) 20) 20     (5 × 4 = 20)           0

이 예에서 결과의 소수 부분은 단위 숫자를 넘어 0을 배당금의 소수 부분인 "내려오기"를 계속하여 계산한다.

이 예는 또한 프로세스의 초기 단계에서 0을 생성하는 단계를 생략할 수 있음을 보여준다. 첫 번째 숫자 1이 칸막이 4보다 작기 때문에 첫 번째 단계는 처음 두 자리 12에 수행된다. 마찬가지로 디비저가 13이라면 12나 1이 아니라 127에 첫발을 내디딘다.

n ÷ m의 긴 분할을 위한 기본 절차

배당 n과 divisor m에서 모든 소수점 위치를 찾는다.
필요한 경우 디비저와 배당금의 십진수를 같은 수의 소수 자릿수로 오른쪽(또는 왼쪽)으로 이동하여 긴 분할 문제를 단순화하여 디비저의 십진수가 마지막 자릿수의 오른쪽에 오도록 한다.
긴 나눗셈을 할 때는 테이블아우 아래에서 위아래로 일직선으로 줄지어 있는 숫자를 유지한다.
각 단계 후 해당 단계의 나머지가 구분자보다 작는지 확인하십시오. 그렇지 않다면 세 가지 가능한 문제가 있다: 곱셈이 틀리거나, 빼기가 틀리거나, 더 큰 몫이 필요하다.
결국, 나머지 r은 점증하는 몫인 r/m에 추가된다.

불변성 특성 및 정확성

프로세스 단계(위)의 기본적인 표시는 결과가 정확함을 보장하는 단계의 속성(특히, q × m + r = n, 여기서 q는 최종 지수이고 r 최종 잔량)보다는 어떤 단계를 수행해야 하는지에 초점을 맞춘다. 약간의 변화된 표현은 더 많은 쓰기가 필요하며, 단순히 지수의 숫자를 업데이트하는 것이 아니라, 우리가 변화를 필요로 하지만, 이러한 단계들이 공정의 중간 지점에서 q × m + r의 평가를 허용함으로써 실제로 정답을 산출하는 이유를 더 명확히 할 수 있다. 이는 알고리즘(아래)의 도출에 사용되는 주요 속성을 보여준다.

구체적으로는 시공 중인 몫의 숫자 뒤의 공백을 최소한 1의 자리까지 메우도록 위의 기본 절차를 수정하고, 그 0을 분할괄호 아래에 기재한 숫자에 포함시킨다.

이를 통해 우리는 모든 단계에서 불변 관계를 유지할 수 있다: q × m + r = n. 여기서 q는 부분구축된 지수(분할대괄호 위)이고, 부분구축된 나머지(분할대괄호 아래 아래쪽 수)이다. 처음에는 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은 더 크다. 다음으로 126보다 작거나 같은 37의 최대 배수가 계산된다. 그래서 3 × 37 = 111 < 126, 그러나 4 × 37 > 126. 복수 111은 126 아래에 쓰여 있고, 3은 해결책이 나타날 곳에 쓰여 있다.

   3         37)1260257        111

이 숫자를 어떤 장소 값 열에 기록하는지 주의 깊게 기록하십시오. 지수의 3은 배당금 1260257의 6과 같은 컬럼(1만 자리)에 들어가는데, 이는 마지막 자릿수인 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

혼합 모드 긴 분할

10진수가 아닌 통화의 경우(1971년 이전의 영국 £SD 시스템 등)와 조치(아보아오이르두푸아 등) 혼합 모드 분할을 사용해야 한다. 50마일 600야드를 37조각으로 나누는 것을 고려하십시오.

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

네 개의 기둥 각각이 차례대로 작업된다. 마일리지부터: 50/37 = 1 나머지 13. 더 이상 분할할 수 없으므로 마일을 야드로 변환하기 위해 1,760만큼 긴 곱셈을 수행하면 결과는 22,880야드 입니다. 이것을 야드 기둥 꼭대기까지 가지고 가서 배당금 23,480으로 600야드에 더해라. 현재 23,480/37의 긴 분할은 634의 정상적인 산출과 나머지 22의 산출로 진행된다. 나머지는 3을 곱하여 발을 얻고 발기둥까지 운반한다. 발을 길게 나누면 1개의 나머지가 29개가 되고, 그 다음엔 12를 곱하면 348인치가 된다. 결과 라인에 15인치의 최종 잔여물이 표시되면서 긴 분할이 계속된다.

소수점 결과 해석

몫이 정수가 아니고 소수점 이상으로 나누기 과정이 연장되면 다음 두 가지 중 하나가 발생할 수 있다.

프로세스가 종료될 수 있으며, 이는 나머지 0에 도달함을 의미한다.
나머지 부분은 소수점 작성 후 발생한 이전 잔차와 동일한 값에 도달할 수 있다. 후자의 경우, 프로세스를 계속하는 것은 무의미할 것이다. 그 시점부터 같은 자릿수 순서가 반복해서 시분에 나타나기 때문이다. 그래서 반복 순서 위에 막대를 그려서 그것이 영원히 반복됨을 표시한다(즉, 모든 이성적인 숫자는 끝 또는 반복적인 소수임).

비영어권 국가의 표기법

중국, 일본, 한국은 인도를 포함한 영어권 국가들과 같은 표기법을 사용한다. 다른 곳에서는 동일한 일반 원칙이 사용되지만, 그 수치는 다르게 배열되는 경우가 많다.

라틴 아메리카

중남미(아르헨티나, 볼리비아, 멕시코, 콜롬비아, 파라과이, 베네수엘라, 우루과이, 브라질 제외)에서는 계산이 거의 정확하게 동일하지만, 위에서 사용한 것과 동일한 두 가지 예시와 함께 아래와 같이 다르게 기재되어 있다. 보통 인용문은 점괘 아래에 그려진 막대 밑에 쓰여진다. 계산의 오른쪽에 긴 수직선이 그려지기도 한다.

     500 ÷ 4 = 125 (설명) 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 (0을 내려옴; 소수점 이하 28) 28 (7 × 4 = 28) 20 (0을 더함) 20 (5 × 4 = 20) 0

멕시코에서는 아래와 같이 뺄셈의 결과만 주석을 달고 정신적으로 계산을 하는 것을 제외하고는 영어권 세계 표기법을 사용한다.

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

볼리비아, 브라질, 파라과이, 베네수엘라, 프랑스어권 캐나다, 콜롬비아, 페루에서는 아래와 같이 유럽식 표기법(아래 참조)을 사용하지만, 이 인용 부위가 수직선으로 구분되지 않는 것을 제외하고는 다음과 같이 표기법을 사용한다.

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

멕시코, 우루과이, 아르헨티나에서도 동일한 절차가 적용되며, 뺄셈의 결과만 주석을 달고 계산은 정신적으로 이루어진다.

유라시아

스페인, 이탈리아, 프랑스, 포르투갈, 리투아니아, 루마니아, 터키, 그리스, 벨기에, 벨라루스, 우크라이나, 러시아에서는 배당자가 배당 오른쪽에 있고 수직 막대로 분리되어 있다. 칸에서도 분열이 일어나지만, 그 몫(결과)은 칸막이 아래에 적혀 있고, 가로줄로 구분되어 있다. 이란, 베트남, 몽골에서도 같은 방법을 쓴다.

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

프랑스뿐만 아니라 키프로스에서도 긴 수직 막대가 6359를 17로 나눈 아래 예에서와 같이 배당금과 이후의 소산들을 시수와 분점으로부터 구분하는데, 이는 374이고 나머지는 1이다.

6	3	5	9	17
− 5	1			374
1	2	5
− 1	1	9
		6	9
	−	6	8
			1

십진수는 직접 나누지 않고, 배당금과 배당금은 10의 힘으로 곱하여 두 개의 정수를 포함한다. 따라서 1명이 12,7을 0,4(소수점대신 사용중)로 나누고 있다면 우선 배당금과 배당금을 127과 4로 바꾸고, 그 다음부터는 위와 같이 분할을 진행하게 된다.

오스트리아, 독일, 스위스에서는 정상 방정식의 공칭적 형식을 사용한다. <dividend> : <divisor> = <divisor>, 콜론 ":"는 분할 연산자에 대한 이진 infix 기호("/" 또는 "÷"로 표시)를 나타낸다. 이러한 지역에서는 소수 구분 기호가 쉼표로 기록된다. (상기 중남미 국가의 첫 번째 섹션, 여기서 사실상 동일한 방식으로 수행됨).

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

덴마크, 노르웨이, 불가리아, 북마케도니아, 폴란드, 크로아티아, 슬로베니아, 헝가리, 체코, 슬로바키아, 베트남, 세르비아에서도 동일한 표기법이 채택되고 있다.

네덜란드에서는 다음과 같은 표기법을 사용한다.

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

임의 기반 알고리즘

모든 $자연수$ n ${\displaystyle$ $n$ $}$ 은(는) $n=\alpha _{0}\alpha _{1}\alpha _{2}...\alpha _{k-1}$ n = $n=\alpha _{0}\alpha _{1}\alpha _{2}...\alpha _{k-1}$ 0 $n=\alpha _{0}\alpha _{1}\alpha _{2}...\alpha _{k-1}$ $n=\alpha _{0}\alpha _{1}\alpha _{2}...\alpha _{k-1}$ $b>1$ $n=\alpha _{0}\alpha _{1}\alpha _{2}...\alpha _{k-1}$ $n=\alpha _{0}\alpha _{1}\alpha _{2}...\alpha _{k-1}$ . . $n=\alpha _{0}\alpha _{1}\alpha _{2}...\alpha _{k-1}$ k $n=\alpha _{0}\alpha _{1}\alpha _{2}...\alpha _{k-1}$ - $n=\alpha _{0}\alpha _{1}\alpha _{2}...\alpha _{k-1}$ ${\$ n $=\{0}\alpha _{1}\alpha _{$ 2}의 순서로 $n=\alpha _{0}\alpha _{1}\alpha _{2}...\alpha _{k-1}$ 임의 $b>1$ 숫자 $b>1$ > $b>1$ 로 $b>1$ 고유하게 나타낼 $n$ $b>1$ 수 $있다$ . $\cHB _{k-1}$ 여기서 $n=\alpha _{0}\alpha _{1}\alpha _{2}...\alpha _{k-1}$ $0\leq \alpha _{i}<b$ $0\leq i<k$ $0\leq \alpha _{i}<b$ $0\leq \alpha _{i}<b$ < b ${\displaystyle 0$ $\leq$ $\$ $property_$ ${i}<b$ $},$ $k$ 서 k ${\$ $displaystyle k$ $}$ 는 $n$ 의 $k$ 자릿수 입니다 $n$ $n$ 및 기본값은 n {\ $displaystyle$ n $}$ 의 값

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

만약 k< n{n\displaystyle} 배당금과 숫자의 6{m\displaystyle}에 나는 내가 어디에{나는\displaystyle}은 수 m{m\displaystyle}이 인자,.;나는{\displaystyle k<, l},=0{\displaystyle q=0}과 r)n{\displaystyle r=n}q. 그렇지 않으면, 우리는 나는 k− ≤ 0≤에서 반복하자.나는{ $\displaystyle 0\leq i\leq k-l}$ 을(를) 중지하기 전에 $0\leq i\leq k-l$

각 반복 $i$ $i$ 에 대해 $i$ $q_{i}$ 까지 $q_{i}$ 한 $q_{i}$ {\ $displaystyle q_{$ i}는 중간 배당 $q_{i}$ , $d_{i}$ $r_{i}$ $d_{i}$ ${\$ 은 $d_{i}$ $($ 는 $r_{i}$ ) 중간 나머지, $\alpha _{i}$ i {\ $displaystyle \alpha_{i}$ 는 원래 $\alpha _{i}$ 배당 다음 자리, a.nd $\beta _{i}$ $\beta _{i}$ ${\$ 은(는) 인수의 다음 자릿수다 $\beta _{i}$ . b 기준 $b$ ${\$ $displaystyle$ $b$ $0\leq \beta _{i}<b$ $0\leq \beta _{i}<b$ < b ${\displaystyle$ 0 $\$ $leq$ $\beta _$ ${i}}.$ 나머지 정의로는 $0\leq r_{i}<m$ ≤ $0\leq r_{i}<m$ $i$ < $m>.$ 모든 값은 자연수다. 우리는 시작한다.

q_{-1}=0

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

$첫$ $l-1$ l $l-1$ - $l-1$ 1 {\ $displaystyle l-1}$ 자리 $l-1$ n ${\displaystyle n$

모든 반복에서, 세 방정식은 진실이다.

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

r_{i}=d_{i}-m\m\m\m\i1}{i}=br_{i-1}+\i1\i1\i1}{i+l-1}-m\i1}{i}}i

q_{i}=bq_{i-1}+\properties _{i}

이러한 $\beta _{i}$ $\beta _{i}$ ${\$ 만 존재하며, $0\leq r_{i}<m$ β $0\leq r_{i}<m$ $<{\displaystyle 0$

$\beta _{i}$ $\beta _{i}$ ${\$ 의 존재 증명 및 고유성

나머지 $r_{i}$ $r_{i}$ ${\$ 의 정의에 따라 $r_{i}$

0\leq r_{i}<m

0\leq br_{i-1}+\pair _{i+l-1}-m\pair _{i

m\property _{i}\leq br_{i-1}+\properties _{i-1}<m(\reason _{i}+1)

불평등 왼쪽으로는 가장 큰 $\beta _{i}$ $\beta _{i}$ ${\$ 를 $\beta _{{i}}$ 선택하여 다음과 같이 한다.

m\property_{i}\leq br_{i-1}+\properties _{i+l-1

$0\leq \beta _{i}<b$ β $0\leq \beta _{i}<b$ $0\leq \beta _{i}<b$ < $0\leq \beta _{i}<b$ > ${\displaystyle 0$ $\leq$ $\beta$ $\beta _{i}$ $_{i}},$ $\beta _{i}=0$ $\beta _{i}=0$ $\beta _{i}=0$ = 0 ${\displaystyle \beta _{i}=$ 0 $\beta _{i}=0$ 그 다음으로는 항상 가장 $\beta _{i}$ 큰 $\beta _{i}$ i가 $\beta _{i}$ .

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

$b>1$ > $b>1$ ${\displaystyle b>1$ $r_{i-1}\geq 0$ i $r_{i-1}\geq 0$ - $r_{i-1}\geq 0$ ≥ $(\displaystyle r_{i-1}\geq 0$ $\alpha _{i+l-1}\geq 0$ $\alpha _{i+l-1}\geq 0$ + l $\alpha _{i+l-1}\geq 0$ - $\alpha _{i+l-1}\geq 0$ $\alpha _{i+l-1}\geq 0$ $(\displaystyle \property_{i+l-1$ }\geq $0$ 이는 항상 사실이다. 불평등의 오른쪽에는 다음과 같은 작은 $\beta _{i}^{\prime }$ $\beta _{i}^{\prime }$ $\beta _{i}^{\prime }$ ′ ${\$ 이(가) 존재한다고 가정한다.

br_{i-1}+\fl_{i+1}<m(\reason _{i}^{\premy }+1)

이 값이 가장 작은 $\beta _{i}^{\prime }$ $\beta _{i}^{\prime }$ β{\ $displaystyle \beta _{i}^{\prime }}$ 불평등이 그대로 유지되므로 $\beta _{i}^{\prime }$ , $\beta _{i}^{\prime }-1$ $\beta _{i}^{\prime }-1$ ′ $\beta _{i}^{\prime }-1$ - $\beta _{i}^{\prime }-1$ 1 {\ $displaystyle \beta _{$ i}^{ $i}-1$ }의 경우 이 값을 의미해야 한다.

br_{i-1}+\preme _{i+l-1}\geq m\preme _{i}^{\premy }}}}

불평등의 왼쪽과 정확히 같은 것이다. Thus, $\beta _{i}=\beta _{i}^{\prime }$ . As $\beta _{i}$ will always exist, so will $\beta _{i}^{\prime }$ equal to $\beta _{i}$ , and there is only one unique $\beta _{i}$ that is v불평등을 조장하다 따라서 우리는 $\beta _{i}$ $\beta _{i}$ ${\$ 의 존재와 고유성을 입증했다 $\beta _{i}$

최종 지수는 $q=q_{k-l}$ = $q=q_{k-l}$ - $q=q_{k-l}$ ${\$ 이며 $q=q_{k-l}$ , 최종 나머지는 $r=r_{k-l}$ = $r=r_{k-l}$ $r=r_{k-l}$ - l ${\$ 이다.

예

베이스 10에서 $n=1260257$ = $n=1260257$ $n=1260257$ 및 $n=1260257$ $m=37$ = $m=37$ $m=37$ 을 $m=37$ 를) 사용한 위의 예를 사용하여 $q_{-1}=0$ 값 Q - $q_{-1}=0$ 1 = $q_{-1}=0$ ${\displaystyle q_$ {- $1}=$ 0 $q_{-1}=0$ } $및$ r - $r_{-1}=1$ = $r_{-1}=1$ ${\displaystyle$ r_{- $1}=$ 1}=1 $}=$ 1 $r_{-1}=1$ 1}= $1}.$

$0\leq i\leq k-l}$	$\alpha _{i+l-1$	$d_{i}=br_{i-1}+\properties _{i+l-1$	$\beta _{i}$	$r_{i}=d_{i}-m\m\cHB_{i}}$	$q_{i}=bq_{i-1}+\properties _{i}$
0	2	$10\cdot 1+2=12$	0	$12-37\cdot 0=12}$	$10\cdot 0+0=0$
1	6	$(\displaystyle 10\cdot 12+6=filename}$	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+Displaystyle 10\cdot 3+4=34}$
3	2	${\displaystaystyle 10\cdot 2+2=22}$	0	$22-37\cdot 0=22}$	$(\displaystyle 10\cdot 34+0=note)}$
4	5	$10\cdot 22+5=messages$	6	$225-37\cdot 6=3}$	$10\cdot 340+6=snv6}$
5	7	$10\cdot 3+displaystyle 10\cdot 3+7=37}$	1	$37-37\cdot 1=0}$	$10\cdot 3406+1=61061$

따라서 $q=34061$ = $q=34061$ $q=34061$ 및 $q=34061$ $r=0$ = 0 ${\displaystyle r=0$

$n={\text{f412df}}$ 16에서 n $n={\text{f412df}}$ = $n={\text{f412df}}$ ${\$ $={\$ $text{f412df}}$ 및 m $n={\text{f412df}}$ $m=12$ = $q_{-1}=0$ $q_{-1}=0$ 및 $r_{-1}={\text{f}}$ 1 $r_{-1}={\text{f}}$ = $q_{-1}=0$ $r_{-1}={\text{f}}$ ${\$

$0\leq i\leq k-l}$	$\alpha _{i+l-1$	$d_{i}=br_{i-1}+\properties _{i+l-1$	$\beta _{i}$	$r_{i}=d_{i}-m\m\cHB_{i}}$	$q_{i}=bq_{i-1}+\properties _{i}$
0	4	$10\cdot {\text{f}+4={\text{f4}}$	${\text{d}$	${\text{f4}-12\cdot {\text{d}={\text{a}}$	$10\cdot 0+{\text}={\text{d}}$
1	1	$10\cdot {\text{a}+1={\text{a1}$	8	${\text1}-12\cdot 8=11$	$10\cdot {\text}+8={\text}$
2	2	$10\cdot 11+2=cd$	${\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}}$ = $q={\text{d8f45}}$ ${\$ $r={\text{5}}$ = $r={\text{5}}$ ${\$ r $={\text{5$

$염기서열$ b에 대한 덧셈, 뺄셈, 곱셈표가 없는 경우에도 숫자를 십진법으로 변환하고 마지막에 다시 염기서열 $b$ 로 변환하면 이 알고리즘은 여전히 작동한다. 예를 들면, 위의 예를 들자면,

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

, 그리고

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

$b=16$ = $b=16$ $[\displaystyle b=16}$ 과(와) 함께 $b=16$ 초기 값은 $q_{-1}=0$ - $q_{-1}=0$ = 0 $q_{-1}=0$ 이고 $q_{-1}=0$ $r_{-1}=15$ - $r_{-1}=15$ = $r_{-1}=15$ $r_{-1}=15$ 입니다 $r_{-1}=15$

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

따라서 $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ = $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ + $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ + $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ + $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ + $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ = $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ $q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}$ ${\$ $}}\cdot 8+16^{2$ $}}\cdot 15+16^{1$ $}\cdot 4+5={\text{d8f45}}_{16},$ $r=5={\text{5}}_{16}$ = 5 $r=5={\text{5}}_{16}$ = 5 $r=5={\text{5}}_{16}$ ${\$

이 알고리즘은 위 절에서와 같은 종류의 연필과 종이 표기를 사용하여 수행할 수 있다.

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

합리적 시세

몫이 정수로 제한되지 않으면 알고리즘은 $i>k-l$ > $i>k-l$ - l $i$ 에 대해 종료되지 않는다 $i>k-l$ 대신, $i>k-l$ > $i>k-l$ - $i>k-l$ ${\displaystyle$ i $>k-l}$ 이면 $i>k-l$ $\alpha _{i}=0$ i $\alpha _{i}=0$ = 0 $\alpha _{i}=0$ 의 정의에 의해 $\alpha _{i}=0$ 종료된다. 나머지 $r_{i}$ $r_{i}$ ${\$ 가 $r_{i}$ 임의의 반복에서 0과 같으면, 그 $b$ 은 b $b$ -adic $b$ fraction이며, base $b$ ${\displaysty b}$ positional $b$ 표기법에서는 유한 소수 확장으로 표현된다. 그렇지 않으면 여전히 합리적인 숫자지만 $b$ $b$ -adic $b$ 합리성은 아니며, 그 대신 $base$ b{\ $displaystyle b}$ positional $b$ 표기법에서 무한 반복적인 소수점 확장으로 표현된다.

이항분할

코스의 각 자릿수는 1 또는 0일 수 있기 때문에 2진수 시스템 내의 계산은 더 간단하다 - 같은 숫자 또는 0으로 결과에 따라 곱셈이 필요하지 않다.

만약 이것이 컴퓨터에 있었다면, $\beta _{i}$ 에 의한 곱셈은 왼쪽으로 1의 비트 이동으로 나타낼 수 있고, $\beta _{i}$ i ${\$ {i $}$ 를 찾으면 논리 연산 d $d_{i}\geq m$ m ${\displaystyle d_{i}\geq$ m $}$ 까지 감소한다 $\beta _{{i}}$ $d_{i}\geq m$ 여기서 true = 1이고 false = 0 = 0. 모든 반복 $0\leq i\leq k-l$ i $0\leq i\leq k-l$ - l $0\leq i\leq k-l$ {\ $displaystyle$ 0 $\leq$ i $\leq$ k-l $}$ 을 $0\leq i\leq k-l$ 를) 사용하여 다음 작업을 수행한다^{[clarification needed]}.

{\regated}\i+l-1}\{{\matht {=}\n\\n\\\mathtt {\\}\(1\{<}}\\mathttt {\>\ (k+1-i-l))\\d_{i}\\\mathtt{=}\r_{i-1}\\\\mathtt{{}\\\mathtt}\{i+l-1}\\\mathtt {\}\{\mathtttt}!}}(d_{i}<m)\\r_{i}\ &{\mathtt {=}}\ d_{i}-m\ {\mathtt {\&}}\ \beta _{I}\\q_{i}\ &{\mathtt {=}}\ q_{i-1}\ {\mathtt {<<}}\ 1+\beta _{I}\end{aligned}}

예를 들어, $n=10111001$ = $n=10111001$ $n=10111001$ $m=1101$ m $n=10111001$ $m=1101$ = $m=1101$ ${\displaystyle m=1101$ }을 $m=1101$ 를) 사용하는 경우 초기 값은 $q_{-1}=0$ - $q_{-1}=0$ = 0 ${\displaystyle q_$ {-1 $}=0$ } $q_{-1}=0$ 및 $r_{-1}=101$ - $r_{-1}=101$ = $r_{-1}=101$ ${\displaystyle r_{-1}=101$ } 입니다 $r_{-1}=101$

$0\leq i\leq k-l}$	$\{i+l-1}\{\mathtt{=}\n\\\\mathtt{\\}\1\<}\i-l)$	$d_{i}\\\matht {=}\r_{i-1}\\\\\mathtt {<}\1+\messages _{i+l-1}$	$\_{i}\ {\matht {=}\!(d_{i}<m)$	$r_{i}\{i}\\\matht {=}\{i}-m\\\matht {\\&}\\\cHB_{i}}}$	$q_{i}\\\matht {=}\q_{i-1}\\\\matht {<}\1+\message _{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

따라서 $q=1110$ = $q=1110$ $q=1110$ 및 $q=1110$ $r=11$ = $r=11$ ${\displaystyle r=11$

퍼포먼스

각 반복에서 가장 많은 시간이 소요되는 작업은 $\beta _{i}$ $\beta _{i}$ ${\$ $_{i$ $}$ 를 $b$ 선택하는 것이다 $\beta _{i}$ 가능한 $b$ 은 b $b$ $O(\log(b))$ O $O(\log(b))$ $O(\log(b))$ ( $){\displaystystyle$ O $(\log(b)})$ 를 $O(\log(b))$ 사용하여 $\beta _{{i}}$ $\beta _{i}$ $\beta _{i}$ ${\\$ 을 찾을 수 있다. 각 비교를 $d_{i}-m\beta _{i}$ d $d_{i}-m\beta _{i}$ - $d_{i}-m\beta _{i}$ $d_{i}-m\beta _{i}$ i $d_{i}-m\beta _{i}$ {\ $displaystyle d_{i}-m\beta _{i}}$ 을(를) 평가해야 한다 $d_{i}-m\beta _{i}$ $k$ {\ $displaystyle k$ }은 $k$ (는) $배당$ n{\ $displaystyle$ $n}$ $l$ l{\ $displaystystyle l}$ 의 자릿수가 되도록 $l$ 한다 $m$ $d_{i}\leq l+1$ $d_{i}\leq l+1$ $d_{i}\leq l+1$ $d_{i}\leq l+1$ + 1 $d_{i}\leq l+1$ 의 자릿수 $d_{i}\leq l+1$ $m\beta _{i}$ $m\beta _{i}$ $m\beta _{i}$ ${\$ 의 곱셈은 $O(l)$ $O(l)$ ( l $O(l)$ ) $O(l)$ 이며 $m\beta _{i}$ $O(l)$ 마찬가지로 $d_{i}-m\beta _{i}$ - $d_{i}-m\beta _{i}$ $d_{i}-m\beta _{i}$ $d_{i}-m\beta _{i}$ ${\$ }의 _{i $}$ 의 뺄셈도 있다 $d_{i}-m\beta _{i}$ 따라서 $O(l\log(b))$ $\beta _{i}$ $\beta _{i}$ ${\$ \beta_{ $i}$ 를 선택하려면 O $O(l\log(b))$ ( $O(l\log(b))$ $O(l\log(b))$ log ( $O(l\log(b))$ ) ${\displaystyle O(l\log(b)})$ 가 필요하다 $\beta _{i}$ The remainder of the algorithm are addition and the digit-shifting of $q_{i}$ and $r_{i}$ to the left one digit, and so takes time $O(k)$ and $O(l)$ in base $b$ , so each iteration takes $O(l\log(b)+k+l)$ $O(l\log(b)+k+l)$ + $O(l\log(b)+k+l)$ + $O(l\log(b)+k+l)$ ) ${\displaystyle O(l\log(b)+$ $O(l\log(b)+k)$ $+l$ 또는 just $O(l\log(b)+k)$ $O(l\log(b)+k)$ log $O(l\log(b)+k)$ (b $O(l\log(b)+k)$ ) $O(l\log(b)+k)$ + k $O(l\log(b)+k)$ ) ${\displaystyle O(l\log(b)+k$ For all $k-l+1$ digits, the algorithm takes time $O((k-1)(l\log(b)+k))$ , or $O(kl\log(b)+k^{2})$ in base $b$ .

일반화

이성수

정수의 긴 분할은 합리적이기만 하면 비정수 배당금을 포함하도록 쉽게 확장할 수 있다. 모든 이성적인 숫자는 반복적으로 소수점 확장이 있기 때문이다. 이 절차는 유한하거나 종료된 소수점 확장(즉, 소수점 분율)을 가진 분수를 포함하도록 확장할 수 있다. 이 경우 절차에는 분배자와 배당금에 10의 적절한 힘을 곱하여 새로운 분배자가 정수가 되도록 하는 것, 즉 ÷ b = (ca) ÷ (cb) – 을 이용하여 위와 같이 진행하는 것이 포함된다.

다항식

다항식 긴 분할이라고 불리는 이 방법의 일반화된 버전은 다항식 분할(때로는 합성 분할이라고 하는 속기 버전을 사용하기도 한다.

참고 항목

알고리즘
임의정밀 산술
이집트 곱셈과 나눗셈
기초 산술
푸리에 분업
다항식 장분할
이동 n번째 루트 알고리즘 - 숫자의 n번째 루트 또는 제곱근을 찾기 위한 알고리즘
단제법

참조

^ Weisstein, Eric W. "Long Division". MathWorld.
^ "Islamic Mathematics". new.math.uiuc.edu. Retrieved 2016-03-31.
^ "Henry Briggs - Oxford Reference". {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)
^ Klein, Milgram. "The Role of Long Division in the K-12 Curriculum" (PDF). CiteSeer. Retrieved June 21, 2019.
^ Nicholson, W. Keith (2012), Introduction to Abstract Algebra, 4th ed., John Wiley & Sons, p. 206.
^ "Long Division Symbol", Wolfram MathWorld, retrieved 11 February 2016.
^ Miller, Jeff (2010), "Symbols of Operation", Earliest Uses of Various Mathematical Symbols.
^ Hill, John (1772) [First published 1712], Arithmetick both in the theory and practice (11th ed.), London: Straben et al., p. 200, retrieved 12 February 2016

외부 링크

[1] Weisstein, Eric W. "Long Division". MathWorld.

[2] "Islamic Mathematics". new.math.uiuc.edu. Retrieved 2016-03-31.

[3] "Henry Briggs - Oxford Reference". {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)

[4] Klein, Milgram. "The Role of Long Division in the K-12 Curriculum" (PDF). CiteSeer. Retrieved June 21, 2019.

[5] Nicholson, W. Keith (2012), Introduction to Abstract Algebra, 4th ed., John Wiley & Sons, p. 206.

[6] "Long Division Symbol", Wolfram MathWorld, retrieved 11 February 2016.

[7] Miller, Jeff (2010), "Symbols of Operation", Earliest Uses of Various Mathematical Symbols.

[8] Hill, John (1772) [First published 1712], Arithmetick both in the theory and practice (11th ed.), London: Straben et al., p. 200, retrieved 12 February 2016

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

v t 수이론적 알고리즘
원시성 검정	AKS APR 바일리-PSW 타원곡선 포클링턴 페르마 루카스 루카스-레머 루카스-레머-리젤 프로트의 정리 페핀스 이차적 프로베니우스 솔로베이-스트라센 밀러-라빈
프라임 생성	앳킨의 체 에라토스테네스의 체 순다람의 체 휠 인자화
정수 인자화	지속분수(CFRAC) 딕슨스 Lenstra 타원 곡선(ECM) 오일러즈 폴라드 호 p − 1 p + 1 2차 체(QS) 일반수 필드 체(GNFS) 특수수 필드 체(SNFS) 이성 체 페르마츠 샨크스의 사각형 재판분할 쇼르스
곱하기	고대 이집트인 긴 카라츠바 툼-쿡 sch나게-스트라센 총통의
유클리드 주 나누기	이진수 청킹 푸리에 골드슈미트 뉴턴-래프슨 긴 짧다 SRT
이산 로그	베이비 스텝 거인 스텝 폴라드 로 폴라드 캥거루 포흘리그-헬먼 지수 미적분학 기능장 체
최대공통점	이진수 유클리드 주 확장유클리드 르메르스
모듈형 제곱근	시폴라 포클링턴스 토넬리-상크스 베를레캄프 쿠네르스
기타 알고리즘	차크라발라 코르나키아 제곱에 의한 지수화 정수 제곱근 정수 관계(LL; KZ) 모듈형 지수 몽고메리 환원 슈프
이탤릭체는 알고리즘이 특수형태의 숫자에 대한 것임을 나타낸다.

Search

장제법

네임스페이스

더

목차

교육

방법