호제법

제목 내뱉기 **호제법**(互除法) 또는 **나눗셈 알고리즘**(division algorithm)은 두 정수 N과 D(각각 분자와 분모)가 주어졌을 때, 나눗셈 정리의 결과인 몫과/또는 나머지를 계산하는 알고리즘이다. 일부는 손으로 적용되며, 다른 일부는 디지털 회로 설계 및 소프트웨어에 사용된다. 호제법은 크게 느린 나눗셈과 빠른 나눗셈의 두 가지 범주로 나뉜다. 느린 호제법은 반복마다 최종 몫의 한 자리를 생성한다. 느린 나눗셈의 예로는 복원, 비수행 복원, 비복원, SRT 나눗셈이 있다. 빠른 나눗셈 방법은 최종 몫에 대한 근사값으로 시작하여 각 반복마다 최종 몫의 두 배 많은 자리를 생성한다.url=https://www.microsoft.com/en-us/research/wp-content/uploads/2008/08/tr-2008-141.pdf 뉴턴-랩슨 및 골드슈미트 알고리즘이 이 범주에 속한다. 이러한 알고리즘의 변형은 빠른 곱셈 알고리즘을 사용하는 것을 허용한다. 그 결과, 큰 정수의 경우 나눗셈에 필요한 컴퓨터 시간은 어떤 곱셈 알고리즘을 사용하든 상관없이 곱셈에 필요한 시간과 상수 계수까지 동일하다. 논의는 N/D = (Q, R)의 형태를 참조하며, 여기서 * N = 분자 (피제수) * D = 분모 (제수) 는 입력이고, * Q = 몫 * R = 나머지 는 출력이다.
# 반복 뺄셈에 의한 나눗셈
역사적으로 에우클레이데스의 원론, 7권, 명제 1에 제시된 최대 공약수 알고리즘에 통합된 가장 간단한 호제법은 두 양의 정수가 주어졌을 때 오직 뺄셈과 비교만을 사용하여 나머지를 찾는다. R := N Q := 0 while R ≥ D do R := R − D Q := Q + 1 end return (Q,R) 몫과 나머지가 존재하고 유일하다는 증명(나눗셈 정리에 설명됨)은 덧셈, 뺄셈, 비교를 사용하여 음수와 양수 모두에 적용 가능한 완전한 호제법을 탄생시킨다. function divide(N, D) if D = 0 then error(DivisionByZero) end if D 0 return divide_unsigned(N, D) end function divide_unsigned(N, D) Q := 0; R := N while R ≥ D do Q := Q + 1 R := R − D end return (Q, R) end 이 절차는 항상 R ≥ 0을 생성한다. 매우 간단하지만, Ω(Q) 단계를 거치므로 장제법과 같은 느린 호제법보다도 기하급수적으로 느리다. Q가 작다고 알려진 경우(출력 민감형 알고리즘이 됨) 유용하며, 실행 가능한 사양 역할을 할 수 있다.
# 장제법
장제법은 십진법으로 표현된 여러 자리 숫자를 종이에 필산으로 나누는 데 사용되는 표준 알고리즘이다. 피제수의 왼쪽 끝에서 오른쪽 끝으로 점진적으로 이동하며, 각 단계에서 제수의 가능한 가장 큰 배수(자릿수 수준에서)를 뺀다. 이 배수들은 몫의 자릿수가 되고, 최종 차이는 나머지가 된다. 이진법 기수와 함께 사용될 때, 이 방법은 아래의 (부호 없는) 정수 나눗셈과 나머지 알고리즘의 기초를 형성한다. 단제법은 한 자리 제수에 적합한 장제법의 단축 형태이다. 덩어리 분할Snd 또는 부분 몫 방법이나 교수형 방법Snd으로도 알려진 이것은 이해하기 쉬울 수 있는 덜 효율적인 장제법 형태이다. 각 단계에서 현재 가진 것보다 더 많은 배수를 뺄 수 있게 함으로써, 보다 자유로운 형태의 장제법도 개발될 수 있다.
## 나머지가 있는 (부호 없는) 정수 나눗셈
다음 알고리즘은 유명한 장제법의 이진 버전으로, N을 D로 나누고 몫을 Q에, 나머지를 R에 저장한다. 다음 유사 코드에서 모든 값은 부호 없는 정수로 취급된다. if D = 0 then error(DivisionByZeroException) end Q := 0 -- Initialize quotient and remainder to zero R := 0 for i := n − 1 .. 0 do -- Where n is number of bits in N R := R =D, 문장 진입
5b단계: R=10 (R−D)
5c단계: Q=10 (Q(i)를 1로 설정) 2단계: i=0으로 설정
3단계: R=100
4단계: R=100
5단계: R>=D, 문장 진입
5b단계: R=0 (R−D)
5c단계: Q=11 (Q(i)를 1로 설정) **끝**
Q=112 (310)이고 R=0.
# 느린 나눗셈 방법
느린 나눗셈 방법은 모두 표준 재귀 방정식에 기반한다language=en :R_{j+1} = B \times R_j - q_{n-(j+1)}\times D , 여기서: * Rj는 나눗셈의 j번째 부분 나머지 * B는 기수 (보통 컴퓨터와 계산기 내부에서는 2) * q n − (j + 1)는 n−(j+1) 위치의 몫의 자릿수이며, 자릿수 위치는 최하위 0부터 최상위 n−1까지 번호가 매겨짐 * n은 몫의 자릿수 * D는 제수
## 복원 나눗셈
복원 나눗셈은 고정소수점 분수 연산을 수행하며 0 = 0 then q(i) := 1 -- 결과 비트 1 else q(i) := 0 -- 결과 비트 0 R := R + D -- 새로운 부분 나머지는 (복원된) 시프트된 값이다 end end \-- 여기서: N = 분자, D = 분모, n = #비트, R = 부분 나머지, q(i) = 몫의 i번째 비트 비수행 복원 나눗셈은 복원 나눗셈과 유사하지만, 2R의 값이 저장되므로 R = 0 then q(i) := +1 R := 2 * R − D else q(i) := −1 R := 2 * R + D end if end \-- 참고: N=분자, D=분모, n=#비트, R=부분 나머지, q(i)=몫의 i번째 비트. 이 알고리즘을 따르면 몫은 −1과 +1로 구성된 비표준 형식이다. 이 형식은 최종 몫을 형성하기 위해 이진수로 변환되어야 한다. 예시: {| border="0" cellpadding="0" |colspan=2 | 다음 몫을 {0,1} 숫자 집합으로 변환: |- |시작: || Q = 111\bar{1}1\bar{1}1\bar{1} |- |1. 양수 항 형성: ||P = 11101010\, |- |2. 음수 항 마스킹:2의 보수가 없는 1의 보수를 사용한 부호 있는 이진 표기법. ||M = 00010101\, |- |3. 빼기: P - M: ||Q = 11010101\, |- |colspan=2 | group=note |} Q의 −1 자리 숫자가 흔히 0으로 저장되는 경우, P는 Q **이며** M 계산은 간단하다. 원래 Q에 대해 1의 보수(비트 단위 보수)를 수행한다. Q := Q − bit.bnot(Q) -- Q의 −1 자릿수가 일반적으로 0으로 표현될 때 적절하다. 마지막으로, 이 알고리즘으로 계산된 몫은 항상 홀수이며, R의 나머지는 −D ≤ R > n이다. (복원 나눗셈과 마찬가지로, R의 하위 비트는 몫 Q의 비트가 생성되는 속도와 동일하게 소모되며, 단일 시프트 레지스터를 둘 다에 사용하는 것이 일반적이다.)
## SRTSRT 나눗셈
SRT 나눗셈은 많은 마이크로프로세서 구현에서 널리 사용되는 나눗셈 방법이다.url-status=liveurl-status=live 이 알고리즘은 IBM의 D. W. 스위니, 일리노이 대학교의 제임스 E. 로버트슨, 임페리얼 칼리지 런던의 K. D. 토처의 이름을 따서 명명되었다. 이들은 대략 같은 시기(각각 1957년 2월, 1958년 9월, 1958년 1월에 발표)에 독립적으로 이 알고리즘을 개발했다.url-status=liveurl-status=live SRT 나눗셈은 비복원 나눗셈과 유사하지만, 피제수와 제수를 기반으로 한 순람표를 사용하여 각 몫 자릿수를 결정한다. 가장 중요한 차이점은 몫에 대해 중복된 표현이 사용된다는 것이다. 예를 들어, 기수 4 SRT 나눗셈을 구현할 때 각 몫 자릿수는 다섯 가지 가능성({ −2, −1, 0, +1, +2 }) 중에서 선택된다. 이 때문에 몫 자릿수의 선택이 완벽할 필요는 없다. 나중의 몫 자릿수가 약간의 오류를 수정할 수 있다. (예를 들어, 몫 자릿수 쌍 (0, +2)와 (1, −2)는 0×4+2 = 1×4−2이므로 동등하다.) 이러한 허용 오차는 전체 폭 뺄셈을 요구하는 대신 피제수와 제수의 몇몇 최상위 비트만을 사용하여 몫 자릿수를 선택할 수 있게 한다. 이러한 단순화는 결국 기수를 2보다 높게 사용할 수 있게 한다. 비복원 나눗셈과 마찬가지로, 최종 단계는 마지막 몫 비트를 해결하기 위한 최종 전체 폭 뺄셈과 몫을 표준 이진 형식으로 변환하는 것이다. 인텔 펜티엄 프로세서의 악명 높은 부동소수점 나눗셈 버그는 잘못 코딩된 순람표 때문에 발생했다. 1066개의 항목 중 5개가 실수로 누락되었다.url-status=liveurl-status=livewebsite=Righto
# 빠른 나눗셈 방법

## 뉴턴-랩슨 나눗셈
뉴턴-랩슨은 뉴턴 방법을 사용하여 D의 역수를 찾고, 그 역수에 N을 곱하여 최종 몫 Q를 찾는다. 뉴턴-랩슨 나눗셈의 단계는 다음과 같다. # 제수 D의 역수 1/D에 대한 추정치 X_0를 계산한다. # 역수의 점점 더 정확한 추정치 X_1,X_2,\ldots,X_S를 계산한다. 여기서 뉴턴-랩슨 방법을 사용한다. # 피제수에 제수의 역수를 곱하여 몫을 계산한다: Q = N X_S. D의 역수를 찾기 위해 뉴턴 방법을 적용하려면 X=1/D에서 영점을 갖는 함수 f(X)를 찾아야 한다. 분명한 함수는 f(X)=DX-1이지만, 이에 대한 뉴턴-랩슨 반복은 D의 역수를 이미 알지 못하면 계산할 수 없기 때문에 도움이 되지 않는다(게다가 반복적 개선을 허용하기보다는 한 단계에서 정확한 역수를 계산하려고 한다). 작동하는 함수는 f(X)=(1/X)-D이며, 이에 대한 뉴턴-랩슨 반복은 다음과 같다. : X_{i+1} = X_i - {f(X_i)\over f'(X_i)} = X_i - {1/X_i - D\over -1/X_i^2} = X_i + X_i(1-DX_i) = X_i(2-DX_i), 이는 X_i로부터 곱셈과 뺄셈만으로 계산하거나 두 개의 융합 곱셈-덧셈을 사용하여 계산할 수 있다. 계산적인 관점에서 표현식 X_{i+1} = X_i + X_i(1-DX_i)와 X_{i+1} = X_i(2-DX_i)는 동등하지 않다. 두 번째 표현식을 사용하여 2n 비트의 정밀도로 결과를 얻으려면 X_i와 (2-DX_i) 사이의 곱셈을 X_i(n 비트)의 주어진 정밀도의 두 배로 계산해야 한다. 반대로, X_i와 (1-DX_i) 사이의 곱셈은 n 비트 정밀도로만 계산하면 된다. 왜냐하면 (1-DX_i)의 선행 n 비트(이진점 이후)는 0이기 때문이다. 오차가 \varepsilon_i = 1 - D X_i로 정의되면 다음과 같다. :\begin{align} \varepsilon_{i+1} &= 1 - D X_{i+1} \\\ &= 1 - D (X_i(2-DX_i)) \\\ &= 1 - 2DX_i + D^2X_i^2 \\\ &= (1 - DX_i)^2 \\\ &= {\varepsilon_i}^2. \\\ \end{align} 각 반복 단계에서 오차의 제곱Snd즉, 뉴턴-랩슨 방법의 소위 이차 수렴Snd은 결과의 정확한 자릿수가 각 반복마다 대략 두 배가 되는 효과를 가져오며, 이는 관련된 숫자가 많은 자릿수를 가질 때(예: 큰 정수 영역에서) 매우 유용해지는 특성이다. 그러나 이는 또한 방법의 초기 수렴이 비교적 느릴 수 있음을 의미하며, 특히 초기 추정치 X_0가 잘못 선택된 경우 더욱 그렇다.
### 초기 추정치
초기 추정치 X_0를 선택하는 하위 문제에 대해, 제수 D에 비트 시프트를 적용하여 0.5 ≤ D ≤ 1이 되도록 스케일링하는 것이 편리하다. 분자 N에 동일한 비트 시프트를 적용하면 몫이 변하지 않음을 보장한다. 제한된 범위 내에 들어오면 간단한 다항식 근사를 사용하여 초기 추정치를 찾을 수 있다. 구간 [0.5,1]에서 최소 최악의 절대 오차를 갖는 선형 근사는 다음과 같다. :X_0 = {48 \over 17} - {32 \over 17} D. 선형 근사 T_0 +T_1 D의 계수는 다음과 같이 결정된다. 오차의 절댓값은 |\varepsilon_0| = |1 - D(T_0 + T_1 D)|이다. 오차의 최대 절댓값의 최솟값은 F(D) = 1 - D(T_0 + T_1 D)에 적용된 체비쇼프 등진동 정리에 의해 결정된다. F(D)의 지역 최소는 F'(D) = 0일 때 발생하며, 해는 D = -T_0/(2T_1)이다. 이 최소 지점에서의 함수 값은 끝점에서의 함수 값과 부호가 반대여야 한다. 즉, F(1/2) = F(1) = -F(-T_0/(2T_1))이다. 두 미지수에 대한 두 방정식은 유일한 해 T_0 = 48/17 및 T_1 = -32/17을 가지며, 최대 오차는 F(1) = 1/17이다. 이 근사를 사용하면 초기 값의 오차 절댓값은 다음보다 작다. :\vert \varepsilon_0 \vert \leq {1 \over 17} \approx 0.059 . 구간에서 1/D에 대한 최적의 이차 근사값은 다음과 같다. : X := \frac{140}{33} - \frac{64}{11} D + \frac{256}{99} D^2. 이것은 오차를 1차 체비쇼프 다항식의 재조정된 3차 다항식과 동일하게 만들도록 선택되었으며, 오차의 절댓값이 1/99 이하가 되도록 한다. 이 개선은 약 \log_2(\log 99/\log 17) \approx 0.7 뉴턴-랩슨 반복과 동일하며, 계산 비용은 한 반복 미만이다. 차수가 2보다 큰 다항식 근사를 생성하는 것이 가능하며, 계수는 레메즈 알고리즘을 사용하여 계산할 수 있다. 여기서의 절충점은 초기 추측에 더 많은 계산 주기가 필요하지만, 뉴턴-랩슨 반복 횟수가 줄어들기를 바라는 것이다. 이 방법의 수렴률이 정확히 이차적이기 때문에, 초기 오차 \varepsilon_0에서 S번의 반복은 다음 정확도로 답을 제공한다. :P = -2^S \log_2 \varepsilon_0 - 1 = 2^S \log_2(1/\varepsilon_0) - 1 이진 자릿수. 일반적인 값은 다음과 같다. {|class=wikitable |+ 역수의 이진 자릿수 정확도 !rowspan=2| \varepsilon_0 ||colspan=5| 반복 |- ! 0 || 1 || 2 || 3 || 4 |- ! 1/17 | 2 | 2 | 2 | 2 | 2 |- ! 1/99 | 2 | 2 | 2 | 2 | 2 |} 이차 초기 추정치에 두 번의 반복을 더하면 IEEE 단정밀도에 충분한 정확도를 제공하지만, 세 번의 반복은 배정밀도에 대해서는 한계가 있다. 선형 초기 추정치에 네 번의 반복을 더하면 이중 및 이중 확장 형식 모두에 충분하다.
### 유사 코드
다음은 N과 D의 몫을 P 이진 자릿수 정밀도로 계산한다. D를 M × 2e로 표현 (여기서 1 ≤ M 1이라고 가정). 반드시 (1/D)를 사용할 필요는 없으며, (1/D)로 환원되는 모든 값 (X/Y)을 사용할 수 있다. 예를 들어, 3으로 나누는 경우 1/3, 2/6, 3/9 또는 194/582와 같은 인수를 사용할 수 있다. 결과적으로, Y가 2의 거듭제곱이면 나눗셈 단계는 빠른 오른쪽 비트 시프트로 줄어든다. N/D를 (N·X)/Y로 계산하는 효과는 나눗셈을 곱셈과 시프트로 대체한다. N·(X/Y)는 0으로 평가되므로 괄호가 중요하다는 점에 유의해야 한다. 하지만 D 자체가 2의 거듭제곱이 아닌 한, 위 조건을 만족하는 X와 Y는 존재하지 않는다. 다행히 (X/Y)가 정확히 1/D와 같지 않더라도 (N·X)/Y는 정수 연산에서 N/D와 정확히 동일한 결과를 제공한다. 이는 근사값에 의해 도입된 오차가 시프트 연산에 의해 버려지는 비트에 포함될 만큼 "충분히 가깝기" 때문이다.url-status=liveurl-status=liveridiculous_fish. "Labor of Division (Episode III): Faster Unsigned Division by Constants" date=2022-01-08. 2011. 배럿 축소는 Y 값에 대해 2의 거듭제곱을 사용하여 Y로 나누는 것을 간단한 오른쪽 시프트로 만든다.url-status=live 제수 D가 2의 거듭제곱이 아닌 일반적인 x-비트 부호 없는 정수 나눗셈의 경우, 다음 항등식은 나눗셈을 두 번의 x-비트 덧셈/뺄셈, 한 번의 x-비트 곱셈(x-비트 결과의 상위 절반만 사용됨) 및 여러 번의 시프트로 변환한다. 이는 k=x+\lceil\log_2{D}\rceil와 a=\left\lceil\frac{2^k}{D}\right\rceil-2^x를 미리 계산한 후에 가능하다. : \left\lfloor\frac{N}{D}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{N-b}{2}\right\rfloor+b}{2^{k-x-1\right\rfloor \text{ where } b=\left\lfloor\frac{Na}{2^x}\right\rfloor 어떤 경우에는 "상수 곱셈"을 시프트 및 덧셈 또는 뺄셈의 연속으로 변환하여 상수로 나누는 것을 훨씬 더 짧은 시간 안에 수행할 수 있다.LaBudde, Robert A.; Golovchenko, Nikolai; Newton, James; and Parker, David; Massmind: "Binary Division by a Constant" date=2022-01-09 특히 10으로 나누는 것이 흥미로운데, 이 경우 나머지가 필요한 경우에도 정확한 몫을 얻을 수 있다.pages=81–85
# 반올림 오차
나눗셈 연산을 수행할 때, 정확한 몫 q와 나머지 r은 컴퓨터의 정밀도 한계에 맞게 근사된다. 호제법은 다음과 같이 명시한다. [ a = bq + r ] 여기서 0 \leq r < |b|이다. 부동소수점 연산에서 몫 q는 \tilde{q}로, 나머지 r은 \tilde{r}로 표현되며, 반올림 오차 \epsilon_q와 \epsilon_r이 발생한다. [ \tilde{q} = q + \epsilon_q ] [ \tilde{r} = r + \epsilon_r ] 이러한 반올림은 작은 오차를 발생시키며, 이는 후속 계산을 통해 전파되고 누적될 수 있다. 이러한 오차는 반복 과정에서, 그리고 거의 동일한 값을 뺄 때 특히 두드러지며, 이를 유효 숫자 손실이라고 한다. 이러한 오차를 완화하기 위해 가드 숫자 또는 고정밀도 산술과 같은 기술이 사용된다.language=Englishjournal=찰스턴 칼리지 부동소수점
# 참고
Notelist
# 추가 자료
* archive-date=2018-07-03 수론 알고리즘 위키데이터 속성 추적 분류:컴퓨터 산술 분류:이진 산술 분류:컴퓨터 산술 알고리즘 분류:나눗셈