장제법

장제법(長除法, Long division) 또는 긴 나눗셈은 산술에서 손으로 수행할 수 있을 만큼 간단한 여러 자리의 수를 나누는 데에 적합한 표준 나눗셈 알고리즘이다. 장제법은 분할 문제를 보다 쉬운 하나의 단계로 세분화한다.

모든 나눗셈 문제에서와 같이 피제수(dividend)라고 부르는 하나의 숫자는 제수(divisor)라고 부르는 다른 숫자에 의해 나뉘어서 몫(quotient)이라는 결과를 낳는다. 그것은 하나의 간단한 단계를 수행하여 임의로 큰 수를 포함하는 계산을 수행할 수 있게 한다. 장제법의 축약된 형태를 단제법(短除法) 또는 짧은 나눗셈이라고 하는데 제수가 한 자리만 있을 때에 거의 항상 장제법 대신에 사용된다. 청킹(Chunking, 부분 할당 방법 또는 행맨 방법이라고도 함)은 영국에서 두드러지는 덜 기계적인 장제법의 양식이며 나눗셈 과정에 대한 보다 전체적인 이해에 기여한다.

12세기 이후에 관련 알고리즘이 존재했지만 현대에 사용되는 특정 알고리즘은 1600년경에 헨리 브릭스에 의해 도입되었다.

교육계

저렴한 계산기와 컴퓨터는 나눗셈 문제를 해결하는 가장 일반적인 방법이 되었는데 종이와 연필을 활용한 전통적인 수학적 연습 방법을 보여주는 교육 기회를 감소시켰다. 내부적으로 이러한 장치는 다양한 나눗셈 알고리즘 중 하나를 사용하며 그 중에서 더 빠른 것은 작업을 달성하기 위해 근사값과 곱셈에 의존한다. 미국에서는 전통적으로 4학년이나 5학년 시기에 도입되었는데 특히 장제법이 개혁 수학에 의해 학교 교과 과정에서 탈락하는 것을 목표로 삼고 있다.

방법

영어권 국가에서는 장제법을 활용하는 과정에서 나눗셈 빗금⟨/⟩ 또는 나눗셈 기호⟨÷⟩를 사용하지 않고 하나의 작품을 연출한다. 제수는 오른쪽 괄호⟨)⟩나 세로 수직선⟨|⟩으로 피제수와 분리되는데 피제수는 괄선에 의해 몫과 분리된다. 이러한 두 기호 간의 조합은 때로 장제법 기호 또는 분할 괄호로 알려져 있다. 이는 18세기에 왼쪽 괄호로 몫으로부터 피제수를 분리한 이전의 단일 선 표기법에서 발전되었다.

이 과정은 피제수의 왼쪽 끝 자리를 제수로 나누는 것부터 시작한다. 몫(정수로 반올림)은 결과의 첫 번째 자리가 되고 나머지는 계산되는데 이 단계는 뺄셈으로 표기되어 있다. 이러한 나머지 부분은 과정이 피제수의 다음 자리(나머지까지의 다음 자리 '내림'으로 표기)에 반복될 때 진행된다. 모든 숫자가 처리되고 나머지가 남지 않으면 과정이 완료된다.

아래에는 500을 4로 나눠서 125가 나오는 나눗셈을 나타내는 예가 나와 있다.

     125      (설명)
   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. 제수 4가 적어도 한 번 들어가는 피제수 500의 왼쪽 끝에서 시작하는 가장 짧은 자릿수를 찾는다. 이 경우 이것은 단순히 1번째 숫자인 5가 된다. 5를 초과하지 않고 제수 4에 곱할 수 있는 가장 큰 숫자는 1이므로 숫자 1을 5보다 위에 두어 몫의 구성을 시작한다.
2. 다음으로 1에 5를 초과하지 않고 4의 배수인 가장 큰 정수를 얻기 위해 1에 4를 곱한다. 그리고 나서 이 4는 5 아래에 놓이고 나머지 1을 얻기 위해 5에서 빼는데 5 아래에 4는 5의 아래에 놓인다.
3. 그 후에 피제수의 사용하지 않는 1번째 자릿수인 5의 뒤에 오는 1번째 자릿수인 0은 바로 자신의 몫과 나머지 1 옆에 복사되어 숫자 10을 형성한다.
4. 이 시점에서 이러한 과정은 정지하는 지점에 도달할 수 있을 정도로 충분히 반복된다. 10을 초과하지 않고 4를 곱할 수 있는 가장 큰 숫자는 2이다. 따라서 2는 가장 왼쪽에 있는 2번째 자릿수가 된다. 여기서 4에 2를 곱하면 8이 되는데 이는 10을 초과하지 않는 4의 가장 큰 배수이다. 따라서 8은 10보다 아래에 쓰여지고 10에서 8을 뺀 나머지 2는 8보다 아래에 놓이게 된다.
5. 피제수의 다음 자리(500의 마지막 0 부분)은 바로 아래로 내려가는데 나머지 2 자리 옆으로 옮겨져서 20을 형성한다. 20을 초과하지 않고 4를 곱할 수 있는 가장 큰 숫자, 즉 5를 가장 왼쪽에서 3번째로 큰 몫의 자리 위에 놓는다. 여기서 5에 4를 곱해서 20을 만든 다음에 20을 쓰고 기존의 20에서 나머지 0을 뺀 다음에 2번째 20을 아래에 쓴다.
6. 여기서 피제수에 더 이상 내릴 자리가 없고 마지막 뺄셈 결과가 0이었으니 과정이 끝났음을 확인할 수 있다.

만약 피제수가 부족한 상황일 때에 마지막으로 남은 것이 0이 아니라면 우리가 2가지 가능한 행동 방식이 존재할 것이다.

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 r 2)
         20     (0을 추가로 내림)
         20     (5 × 4 = 20)
          0

이 예제에서 결과의 소수 부분은 단위 자릿수를 넘어 0을 피제수의 소수 부분인 "내림"하는 과정을 계속하여 계산된다. 또한 이 예제는 과정을 시작하는 과정에서 0을 생성하는 단계를 생략할 수 있음을 보여준다. 1번째 자릿수 1이 자릿수 4보다 작기 때문에 1번째 단계는 처음 두 자릿수 12에서 대신 수행한다. 마찬가지로 제수가 13이면 12 또는 1이 아니라 127에서 첫 번째 단계를 수행한다.

n ÷ m의 장제법을 위한 기본 절차

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

불변속성 및 정확성

과정 단계(위쪽)의 기본 표시는 결과가 정확함을 보장하는 "단계의 속성"보다는 "어떠한" 단계를 수행해야 하는지에 초점을 맞춘다(특히 q × m + r = n, 여기서 q는 최종 몫이고 r은 마지막 몫이다). 프레젠테이션 과정에서의 약간의 변화는 더 많은 쓰기를 요구하며 우리는 단순히 인용구의 숫자를 업데이트하는 것이 아니라 우리가 변경하도록 요구하지만 이러한 단계들이 프로세스의 중간 지점에서 "q & times; m + r"의 평가를 허용함으로써 실제로 올바른 답을 도출하는 "왜"를 더 많이 보여줄 수 있다. 이것은 알고리즘의 파생에 사용되는 주요 속성을 보여준다 (아래쪽),.

구체적으로 우리는 위의 기본 절차를 수정하여 시공 중인 "몫"의 자릿수 뒤에 0을 적어도 1의 자리로 채우고 그러한 0을 분할 괄호 아래에 쓰는 숫자에 포함시키도록 한다.

이를 통해 우리는 q × m + r = n과 모든 단계에서 불변량을 유지할 수 있다. 여기서 "q"는 부분 분할된 몫(분할 괄호 위쪽)이고, "r"은 부분 분할된 나머지(분할 괄호 아래쪽에 나와 있는 번호)이다. 처음에는 q=0과 r=n이 유지되기 때문에 이러한 속성은 처음에 유지된다. 이 프로세스는 각 단계에서 r을 줄이고 q를 증가시킨다. 우리가 몫 + 정수 나머지 형태로 답을 찾는다면 결국 r=m이 될 때 중단된다.

위의 "500 ÷ 4" 예제를 다시 살펴보자.

     125      (q, 아래와 같이 000을 100, 120, 125 순으로 변경한다.)
   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=120, r= 20이면 q×4+r = 500이 된다.)
      20      (  4 ×   5 =  20)
       0      ( 20 -  20 =   0;  q=125, r=  0이면 q×4+r = 500이 된다.)

여러 자리 구분 기호 예제

장제법의 예제를 보여주는 애니메이션

자릿수 구분 기호를 사용할 수 있다. 이 예제에서는 1,260,257을 37로 나눈다. 먼저 다음과 같이 문제가 설정된다.

              
    37)1260257

숫자 1,260,257의 자릿수는 37보다 크거나 같은 숫자가 발생할 때까지 계산된다. 그래서 1과 12는 37보다 적지만 126은 더 크다. 다음으로 126보다 작거나 같은 37의 최대 배수가 계산된다. 따라서 3 & times; 37 = 111 < 126이지만 4 & times; 37 > 126이다. 다중적인 111은 126 아래에 기록되고 3은 해답이 나타나는 위쪽에 기록된다.

         3    
    37)1260257
       111

이 숫자가 어느 자리값 선에 입력되었는지 주의 깊게 기록한다. 몫의 3은 피제수 1,260,257의 6과 같은 선(1만 자리)에 속하며 이는 마지막 자리인 111과 같은 선이다. 그런 다음에 위쪽 선에서 111을 빼면서 오른쪽에 있는 모든 숫자를 무시한다.

         3    
    37)1260257
       111
        15

다음으로 작은 피제수의 자리 값에서 나온 자릿수가 복사되어 결과 15에 추가된다.

         3    
    37)1260257
       111
        150

과정 반복: 37의 최대 배수가 150보다 작거나 같은 값을 뺀다. 이 값은 148 = 4 & times; 37이므로 다음 자릿수로 위에 4를 추가한다. 뺄샘 결과는 피제수에서 추출한 다른 숫자로 확장된다.

         34   
    37)1260257
       111
        150
        148
          22

37이 22보다 작거나 같은 최대 배수는 0 & 곱; 37 = 0이다. 22에서 0을 빼면 22가 주어지므로 종종 뺄셈 단계를 쓰지 않는다. 그 대신 피제수에서 다른 숫자를 빼면 된다.

         340  
    37)1260257
       111
        150
        148
          225

37이 마지막 선을 정확히 나눌 때까지 과정이 반복된다.

         34061
    37)1260257
       111
        150
        148
          225
          222
            37

혼합 모드 장제법

십진수 이외의 통화(예: 1971년 이전의 영국 파운드 스털링 시스템) 및 측정(예: 상형) 과정에서는 혼합 모드를 사용해야 한다. 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
                   ==

4개의 기둥 각각이 차례대로 작업한다. 마일부터 시작하면 50/37 = 1 나머지 13이라는 등식이 나온다. 더 이상 분할이 불가능하므로 마일을 야드로 변환하기 위해 1,760의 긴 곱셈을 수행한다. 결과는 22,880야드이다. 이것을 야드 기둥의 맨 위까지 옮겨서 피제수 600야드에 23,480을 더한다. 23,480 / 37의 장제법은 현재 634의 나머지 22를 산출하고 정상적으로 진행된다. 나머지는 3을 곱해 몫을 얻고 몫의 기둥까지 옮겨진다. 몫의 장제법은 1의 나머지를 29로 주고 그 다음에 12를 곱하면 348인치가 된다. 긴 편차는 계속되며 마지막으로 남은 15인치는 결과 줄에 표시된다.

소수점 결과 해석

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

1. 프로세스가 종료될 수 있다. 즉 나머지가 0에 도달한다. 또는
2. 소수점 작성 이후에 발생한 이전 나머지와 동일한 나머지에 도달할 수 있다. 후자의 경우 과정을 계속하는 것은 무의미할 수 있는데 왜냐하면 그 시점 이후부터는 같은 자릿수의 순서가 반복하여 몫에 나타나기 때문이다. 따라서 반복되는 순서 위에 막대가 그려져 영원히 반복됨을 나타낸다(즉 모든 유리수는 종료되거나 순환소수이다).

임의 베이스 알고리즘

모든 자연수 $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$이면 $0\leq \beta _{i}<b$이기 때문에 항상 가장 큰 $\beta _{i}$가 존재한다. 따라서

$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}$이다.

예제

십진법에서 위와 같은 예를 따라 $n=1,260,257$과 $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=34,061$는 $r=0$이다.

십육진법에서 $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}$가 반복해서 0과 같으면 몫은 $b$-진 유리수가 되고 $b$ 위치 표기법에 기초한 유한 소수 확장이 된다. 그렇지 않으면 이것은 여전히 유리수이지만 $b$-진 유리수가 아니며 대신 $b$ 위치 표기법에 기초한 무한 반복 소수 확장이 된다.

이항 분할

이진법 체계의 계산은 더 간단하다. 왜냐하면 경로의 각 자릿수는 1 또는 0이기 때문인데 항등원 또는 흡수원 가운데 하나의 결과로 곱할 필요가 없기 때문이다.

만약 이것이 컴퓨터에서라면 10의 곱셈은 1이 왼쪽으로 비트 이동을 하는 현상을 나타낼 수 있는데 $\beta _{i}$은 논리 연산을 통해 감소되어 $d_{i}\geq m$으로 바뀜을 표현한다. 여기서 참 = 1, 거짓 = 0이라는 등식을 찾아낼 수 있다. 또한 $0\leq i\leq k-l$이 반복되는 현상을 표현하기 위하여 다음 작업이 수행된다.

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

예를 들어 $n=10111001$이고 $m=1101$일 때 초기의 값 $q_{-1}=0$ 및 $r_{-1}=101$를 사용한다.

$0\leq i\leq k-l$	$\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 {=}}\ !(d_{i}<m)$	$r_{i}\ {\mathtt {=}}\ d_{i}-m\ {\mathtt {\&}}\ \beta _{i}$	$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

따라서 $q=1,110$이고 $r=11$이다.

성과

각 반복에서 가장 많은 시간이 걸리는 작업은 $\beta _{i}$를 선택하는 것이다. 우리는 가능한 값이 있다는 것을 알고 있으므로 $O(\log(b))$를 사용하여 $\beta _{i}$를 찾을 수 있다. 각 비교 과정에서는 $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)$을 취한다. 모든 $k-l+1$ 자리에서 알고리즘은 $O((k-1)(l\log(b)+k))$ 또는 $O(kl\log(b)+k^{2})$의 몫 $b$을 취한다.

일반화

유리수

정수의 장제법은 유리수이기만 하면 비정수 피제수를 포함하도록 쉽게 확장될 수 있다. 이는 모든 유리수에는 반복적인 순환소수가 있기 때문이다. 또한 이 절차는 유한하거나 종단하는 십진법 확장(즉 소수 분수)을 갖는 제수를 포함하도록 확장될 수 있다. 이러한 절차에는 a ÷ b = (ca) ÷ (cb) –라는 사실을 이용하여 새로운 제수가 정수가 되도록 제수와 피제수에 10의 적절한 거듭제곱을 곱한 다음에 위와 같이 진행한다.

다항식

다항식 장제법이라고 부르는 장제법의 일반화된 버전은 다항식을 나누는 데에도 사용된다(때로는 조립제법이라고 부르는 버전을 사용하기도 한다).

외부 링크

• Long Division Algorithm
• Long Division and Euclid's Lemma