호제법

다른 뜻에 대해서는 제목 내뱉기 문서를 참고하십시오.

호제법(互除法) 또는 나눗셈 알고리즘(division algorithm)은 두 정수 N과 D(각각 분자와 분모)가 주어졌을 때, 나눗셈 정리의 결과인 몫과/또는 나머지를 계산하는 알고리즘이다. 일부는 손으로 적용되며, 다른 일부는 디지털 회로 설계 및 소프트웨어에 사용된다.

호제법은 크게 느린 나눗셈과 빠른 나눗셈의 두 가지 범주로 나뉜다. 느린 호제법은 반복마다 최종 몫의 한 자리를 생성한다. 느린 나눗셈의 예로는 복원, 비수행 복원, 비복원, SRT 나눗셈이 있다. 빠른 나눗셈 방법은 최종 몫에 대한 근사값으로 시작하여 각 반복마다 최종 몫의 두 배 많은 자리를 생성한다.^[1] 뉴턴-랩슨 및 골드슈미트 알고리즘이 이 범주에 속한다.

이러한 알고리즘의 변형은 빠른 곱셈 알고리즘을 사용하는 것을 허용한다. 그 결과, 큰 정수의 경우 나눗셈에 필요한 컴퓨터 시간은 어떤 곱셈 알고리즘을 사용하든 상관없이 곱셈에 필요한 시간과 상수 계수까지 동일하다.

논의는 ${\displaystyle 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 then (Q, R) := divide(N, −D); return (−Q, R) end
  if N < 0 then
    (Q,R) := divide(−N, D)
    if R = 0 then return (−Q, 0)
    else return (−Q − 1, D − R) end
  end
  -- At this point, N ≥ 0 and 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가 작다고 알려진 경우(출력 민감형 알고리즘이 됨) 유용하며, 실행 가능한 사양 역할을 할 수 있다.

장제법

장제법은 십진법으로 표현된 여러 자리 숫자를 종이에 필산으로 나누는 데 사용되는 표준 알고리즘이다. 피제수의 왼쪽 끝에서 오른쪽 끝으로 점진적으로 이동하며, 각 단계에서 제수의 가능한 가장 큰 배수(자릿수 수준에서)를 뺀다. 이 배수들은 몫의 자릿수가 되고, 최종 차이는 나머지가 된다.

이진법 기수와 함께 사용될 때, 이 방법은 아래의 (부호 없는) 정수 나눗셈과 나머지 알고리즘의 기초를 형성한다. 단제법은 한 자리 제수에 적합한 장제법의 단축 형태이다. 덩어리 분할 – 또는 부분 몫 방법이나 교수형 방법 – 으로도 알려진 이것은 이해하기 쉬울 수 있는 덜 효율적인 장제법 형태이다. 각 단계에서 현재 가진 것보다 더 많은 배수를 뺄 수 있게 함으로써, 보다 자유로운 형태의 장제법도 개발될 수 있다.

나머지가 있는 (부호 없는) 정수 나눗셈

 이진법 § 나눗셈 문서를 참고하십시오.

다음 알고리즘은 유명한 장제법의 이진 버전으로, 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 << 1           -- Left-shift R by 1 bit
  R(0) := N(i)          -- Set the least-significant bit of R equal to bit i of the numerator
  if R ≥ D then
    R := R − D
    Q(i) := 1
  end
end

예시

N=1100₂ (12₁₀)이고 D=100₂ (4₁₀)인 경우

1단계: R=0, Q=0으로 설정
2단계: i=3으로 설정 (N의 비트 수보다 하나 작음)
3단계: R=00 (왼쪽으로 1비트 시프트)
4단계: R=01 (R(0)을 N(i)로 설정)
5단계: R < D, 문장 건너뜀

2단계: i=2로 설정
3단계: R=010
4단계: R=011
5단계: R < D, 문장 건너뜀

2단계: i=1로 설정
3단계: R=0110
4단계: R=0110
5단계: 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=11₂ (3₁₀)이고 R=0.

느린 나눗셈 방법

느린 나눗셈 방법은 모두 표준 재귀 방정식에 기반한다^[2]

${\displaystyle R_{j+1}=B\times R_{j}-q_{n-(j+1)}\times D,}$

여기서:

• R_j는 나눗셈의 j번째 부분 나머지
• B는 기수 (보통 컴퓨터와 계산기 내부에서는 2)
• q _{n − (j + 1)}는 n−(j+1) 위치의 몫의 자릿수이며, 자릿수 위치는 최하위 0부터 최상위 n−1까지 번호가 매겨짐
• n은 몫의 자릿수
• D는 제수

복원 나눗셈

복원 나눗셈은 고정소수점 분수 연산을 수행하며 0 < D < N이라는 가정에 의존한다.

몫 자리 q는 {0,1}의 숫자 집합으로 형성된다.

이진수 (기수 2) 복원 나눗셈의 기본 알고리즘은 다음과 같다.

R := N
D := D << n            -- R과 D는 N과 Q의 두 배 워드 너비가 필요하다
for i := n − 1 .. 0 do  -- 예를 들어 32비트의 경우 31..0
  R := 2 * R − D          -- 시프트된 값에서 시험 뺄셈 (2를 곱하는 것은 이진 표현에서 시프트이다)
  if R >= 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인 경우 D를 다시 더할 필요가 없다.

비복원 나눗셈

비복원 나눗셈은 몫 자릿수에 {0, 1} 대신 {−1, 1} 집합을 사용한다. 이 알고리즘은 더 복잡하지만, 하드웨어로 구현할 때 몫 비트당 하나의 결정과 덧셈/뺄셈만 있으면 된다는 장점이 있다. 뺄셈 후 복원 단계가 없어^[3] 잠재적으로 연산 횟수를 절반까지 줄여 더 빠르게 실행할 수 있다.^[4] 음수가 아닌 숫자에 대한 이진(기수 2) 비복원 나눗셈의 기본 알고리즘은 다음과 같다.^{[확인 필요]}

R := N
D := D << n            -- R과 D는 N과 Q의 두 배 워드 너비가 필요하다
for i = n − 1 .. 0 do  -- 예를 들어 32비트의 경우 31..0
  if 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로 구성된 비표준 형식이다. 이 형식은 최종 몫을 형성하기 위해 이진수로 변환되어야 한다. 예시:

다음 몫을 {0,1} 숫자 집합으로 변환:
시작:	${\displaystyle Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}}$
1. 양수 항 형성:	${\displaystyle P=11101010\,}$
2. 음수 항 마스킹:[주 1]	${\displaystyle M=00010101\,}$
3. 빼기: ${\displaystyle P-M}$:	${\displaystyle Q=11010101\,}$

${\displaystyle Q}$의 −1 자리 숫자가 흔히 0으로 저장되는 경우, ${\displaystyle P}$는 ${\displaystyle Q}$ 이며 ${\displaystyle M}$ 계산은 간단하다. 원래 ${\displaystyle Q}$에 대해 1의 보수(비트 단위 보수)를 수행한다.

Q := Q − bit.bnot(Q)      -- Q의 −1 자릿수가 일반적으로 0으로 표현될 때 적절하다.

마지막으로, 이 알고리즘으로 계산된 몫은 항상 홀수이며, R의 나머지는 −D ≤ R < D 범위에 있다. 예를 들어, 5 / 2 = 3 R −1이다. 양의 나머지로 변환하려면, Q가 비표준 형식에서 표준 형식으로 변환된 후 단일 복원 단계를 수행한다.

if R < 0 then
  Q := Q − 1
  R := R + D  -- 나머지에 관심이 있는 경우에만 필요하다.
end if

실제 나머지는 R >> n이다. (복원 나눗셈과 마찬가지로, R의 하위 비트는 몫 Q의 비트가 생성되는 속도와 동일하게 소모되며, 단일 시프트 레지스터를 둘 다에 사용하는 것이 일반적이다.)

SRT 나눗셈

SRT 나눗셈은 많은 마이크로프로세서 구현에서 널리 사용되는 나눗셈 방법이다.^[5][6] 이 알고리즘은 IBM의 D. W. 스위니, 일리노이 대학교의 제임스 E. 로버트슨, 임페리얼 칼리지 런던의 K. D. 토처의 이름을 따서 명명되었다. 이들은 대략 같은 시기(각각 1957년 2월, 1958년 9월, 1958년 1월에 발표)에 독립적으로 이 알고리즘을 개발했다.^[7][8][9]

SRT 나눗셈은 비복원 나눗셈과 유사하지만, 피제수와 제수를 기반으로 한 순람표를 사용하여 각 몫 자릿수를 결정한다.

가장 중요한 차이점은 몫에 대해 중복된 표현이 사용된다는 것이다. 예를 들어, 기수 4 SRT 나눗셈을 구현할 때 각 몫 자릿수는 다섯 가지 가능성({ −2, −1, 0, +1, +2 }) 중에서 선택된다. 이 때문에 몫 자릿수의 선택이 완벽할 필요는 없다. 나중의 몫 자릿수가 약간의 오류를 수정할 수 있다. (예를 들어, 몫 자릿수 쌍 (0, +2)와 (1, −2)는 0×4+2 = 1×4−2이므로 동등하다.) 이러한 허용 오차는 전체 폭 뺄셈을 요구하는 대신 피제수와 제수의 몇몇 최상위 비트만을 사용하여 몫 자릿수를 선택할 수 있게 한다. 이러한 단순화는 결국 기수를 2보다 높게 사용할 수 있게 한다.

비복원 나눗셈과 마찬가지로, 최종 단계는 마지막 몫 비트를 해결하기 위한 최종 전체 폭 뺄셈과 몫을 표준 이진 형식으로 변환하는 것이다.

인텔 펜티엄 프로세서의 악명 높은 부동소수점 나눗셈 버그는 잘못 코딩된 순람표 때문에 발생했다. 1066개의 항목 중 5개가 실수로 누락되었다.^[10][11][12]

빠른 나눗셈 방법

뉴턴-랩슨 나눗셈

뉴턴-랩슨은 뉴턴 방법을 사용하여 ${\displaystyle D}$의 역수를 찾고, 그 역수에 ${\displaystyle N}$을 곱하여 최종 몫 ${\displaystyle Q}$를 찾는다.

뉴턴-랩슨 나눗셈의 단계는 다음과 같다.

1. 제수 ${\displaystyle D}$의 역수 ${\displaystyle 1/D}$에 대한 추정치 ${\displaystyle X_{0}}$를 계산한다.
2. 역수의 점점 더 정확한 추정치 ${\displaystyle X_{1},X_{2},\ldots ,X_{S}}$를 계산한다. 여기서 뉴턴-랩슨 방법을 사용한다.
3. 피제수에 제수의 역수를 곱하여 몫을 계산한다: ${\displaystyle Q=NX_{S}}$.

${\displaystyle D}$의 역수를 찾기 위해 뉴턴 방법을 적용하려면 ${\displaystyle X=1/D}$에서 영점을 갖는 함수 ${\displaystyle f(X)}$를 찾아야 한다. 분명한 함수는 ${\displaystyle f(X)=DX-1}$이지만, 이에 대한 뉴턴-랩슨 반복은 ${\displaystyle D}$의 역수를 이미 알지 못하면 계산할 수 없기 때문에 도움이 되지 않는다(게다가 반복적 개선을 허용하기보다는 한 단계에서 정확한 역수를 계산하려고 한다). 작동하는 함수는 ${\displaystyle f(X)=(1/X)-D}$이며, 이에 대한 뉴턴-랩슨 반복은 다음과 같다.

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

이는 ${\displaystyle X_{i}}$로부터 곱셈과 뺄셈만으로 계산하거나 두 개의 융합 곱셈-덧셈을 사용하여 계산할 수 있다.

계산적인 관점에서 표현식 ${\displaystyle X_{i+1}=X_{i}+X_{i}(1-DX_{i})}$와 ${\displaystyle X_{i+1}=X_{i}(2-DX_{i})}$는 동등하지 않다. 두 번째 표현식을 사용하여 2n 비트의 정밀도로 결과를 얻으려면 ${\displaystyle X_{i}}$와 ${\displaystyle (2-DX_{i})}$ 사이의 곱셈을 ${\displaystyle X_{i}}$(n 비트)의 주어진 정밀도의 두 배로 계산해야 한다. 반대로, ${\displaystyle X_{i}}$와 ${\displaystyle (1-DX_{i})}$ 사이의 곱셈은 n 비트 정밀도로만 계산하면 된다. 왜냐하면 ${\displaystyle (1-DX_{i})}$의 선행 n 비트(이진점 이후)는 0이기 때문이다.

오차가 ${\displaystyle \varepsilon _{i}=1-DX_{i}}$로 정의되면 다음과 같다.

${\displaystyle {\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-D(X_{i}(2-DX_{i}))\\&=1-2DX_{i}+D^{2}X_{i}^{2}\\&=(1-DX_{i})^{2}\\&={\varepsilon _{i}}^{2}.\\\end{aligned}}}$

각 반복 단계에서 오차의 제곱 – 즉, 뉴턴-랩슨 방법의 소위 이차 수렴 – 은 결과의 정확한 자릿수가 각 반복마다 대략 두 배가 되는 효과를 가져오며, 이는 관련된 숫자가 많은 자릿수를 가질 때(예: 큰 정수 영역에서) 매우 유용해지는 특성이다. 그러나 이는 또한 방법의 초기 수렴이 비교적 느릴 수 있음을 의미하며, 특히 초기 추정치 ${\displaystyle X_{0}}$가 잘못 선택된 경우 더욱 그렇다.

초기 추정치

초기 추정치 ${\displaystyle X_{0}}$를 선택하는 하위 문제에 대해, 제수 D에 비트 시프트를 적용하여 0.5 ≤ D ≤ 1이 되도록 스케일링하는 것이 편리하다. 분자 N에 동일한 비트 시프트를 적용하면 몫이 변하지 않음을 보장한다. 제한된 범위 내에 들어오면 간단한 다항식 근사를 사용하여 초기 추정치를 찾을 수 있다.

구간 ${\displaystyle [0.5,1]}$에서 최소 최악의 절대 오차를 갖는 선형 근사는 다음과 같다.

${\displaystyle X_{0}={48 \over 17}-{32 \over 17}D.}$

선형 근사 ${\displaystyle T_{0}+T_{1}D}$의 계수는 다음과 같이 결정된다. 오차의 절댓값은 ${\displaystyle |\varepsilon _{0}|=|1-D(T_{0}+T_{1}D)|}$이다. 오차의 최대 절댓값의 최솟값은 ${\displaystyle F(D)=1-D(T_{0}+T_{1}D)}$에 적용된 체비쇼프 등진동 정리에 의해 결정된다. ${\displaystyle F(D)}$의 지역 최소는 ${\displaystyle F'(D)=0}$일 때 발생하며, 해는 ${\displaystyle D=-T_{0}/(2T_{1})}$이다. 이 최소 지점에서의 함수 값은 끝점에서의 함수 값과 부호가 반대여야 한다. 즉, ${\displaystyle F(1/2)=F(1)=-F(-T_{0}/(2T_{1}))}$이다. 두 미지수에 대한 두 방정식은 유일한 해 ${\displaystyle T_{0}=48/17}$ 및 ${\displaystyle T_{1}=-32/17}$을 가지며, 최대 오차는 ${\displaystyle F(1)=1/17}$이다. 이 근사를 사용하면 초기 값의 오차 절댓값은 다음보다 작다.

${\displaystyle \vert \varepsilon _{0}\vert \leq {1 \over 17}\approx 0.059.}$

구간에서 ${\displaystyle 1/D}$에 대한 최적의 이차 근사값은 다음과 같다.

${\displaystyle X:={\frac {140}{33}}-{\frac {64}{11}}D+{\frac {256}{99}}D^{2}.}$

이것은 오차를 1차 체비쇼프 다항식의 재조정된 3차 다항식과 동일하게 만들도록 선택되었으며, 오차의 절댓값이 1/99 이하가 되도록 한다. 이 개선은 약 ${\displaystyle \log _{2}(\log 99/\log 17)\approx 0.7}$ 뉴턴-랩슨 반복과 동일하며, 계산 비용은 한 반복 미만이다.

차수가 2보다 큰 다항식 근사를 생성하는 것이 가능하며, 계수는 레메즈 알고리즘을 사용하여 계산할 수 있다. 여기서의 절충점은 초기 추측에 더 많은 계산 주기가 필요하지만, 뉴턴-랩슨 반복 횟수가 줄어들기를 바라는 것이다.

이 방법의 수렴률이 정확히 이차적이기 때문에, 초기 오차 ${\displaystyle \varepsilon _{0}}$에서 ${\displaystyle S}$번의 반복은 다음 정확도로 답을 제공한다.

${\displaystyle P=-2^{S}\log _{2}\varepsilon _{0}-1=2^{S}\log _{2}(1/\varepsilon _{0})-1}$

이진 자릿수. 일반적인 값은 다음과 같다.

역수의 이진 자릿수 정확도

${\displaystyle \varepsilon _{0}}$	반복
	0	1	2	3	4
${\displaystyle 1/17}$	3.09	7.17	15.35	31.70	64.40
${\displaystyle 1/99}$	5.63	12.26	25.52	52.03	105.07

이차 초기 추정치에 두 번의 반복을 더하면 IEEE 단정밀도에 충분한 정확도를 제공하지만, 세 번의 반복은 배정밀도에 대해서는 한계가 있다. 선형 초기 추정치에 네 번의 반복을 더하면 이중 및 이중 확장 형식 모두에 충분하다.

유사 코드

다음은 N과 D의 몫을 P 이진 자릿수 정밀도로 계산한다.

D를 M × 2e로 표현 (여기서 1 ≤ M < 2) (표준 부동소수점 표현)
D' := D / 2e+1   // 0.5와 1 사이로 스케일 조정, 비트 시프트 / 지수 뺄셈으로 수행 가능
N' := N / 2e+1
X := 48/17 − 32/17 × D'   // D와 동일한 정밀도로 상수 사전 계산
repeat ${\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}$ times   // 고정된 P에 기반하여 사전 계산 가능
    X := X + X × (1 - D' × X)
end
return N' × X

예를 들어, 배정밀도 부동소수점 나눗셈의 경우 이 방법은 10번의 곱셈, 9번의 덧셈, 2번의 시프트를 사용한다.

3차 반복

오차를 세 제곱하는 데 세 번의 곱셈을 사용하는 반복이 있다.

${\displaystyle \varepsilon _{i}=1-DX_{i}}$

${\displaystyle Y_{i}=X_{i}\varepsilon _{i}}$

${\displaystyle X_{i+1}=X_{i}+Y_{i}+Y_{i}\varepsilon _{i}.}$

${\displaystyle Y_{i}\varepsilon _{i}}$ 항이 새로 추가되었다.

위를 전개하면 ${\displaystyle X_{i+1}}$는 다음과 같이 쓸 수 있다.

${\displaystyle {\begin{aligned}X_{i+1}&=X_{i}+X_{i}\varepsilon _{i}+X_{i}\varepsilon _{i}^{2}\\&=X_{i}+X_{i}(1-DX_{i})+X_{i}(1-DX_{i})^{2}\\&=3X_{i}-3DX_{i}^{2}+D^{2}X_{i}^{3},\end{aligned}}}$

그 결과 오차 항은

${\displaystyle {\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-3DX_{i}+3D^{2}X_{i}^{2}-D^{3}X_{i}^{3}\\&=(1-DX_{i})^{3}\\&=\varepsilon _{i}^{3}.\end{aligned}}}$

이는 2차 반복의 3/2 계산이지만, ${\displaystyle \log 3/\log 2\approx 1.585}$만큼 더 많은 수렴을 달성하므로 약간 더 효율적이다. 달리 말해, 이 방법을 두 번 반복하면 오차가 아홉 제곱으로 증가하는 반면, 세 번의 2차 반복은 오차를 여덟 제곱으로만 증가시킨다.

${\displaystyle S}$번의 반복 후 정확한 비트 수는 다음과 같다.

${\displaystyle P=-3^{S}\log _{2}\varepsilon _{0}-1=3^{S}\log _{2}(1/\varepsilon _{0})-1}$

이진 자릿수. 일반적인 값은 다음과 같다.

역수의 비트 정확도

${\displaystyle \varepsilon _{0}}$	반복
	0	1	2	3
${\displaystyle 1/17}$	3.09	11.26	35.79	109.36
${\displaystyle 1/99}$	5.63	18.89	58.66	177.99

이차 초기 추정치와 두 번의 3차 반복은 IEEE 배정밀도 결과에 충분한 정밀도를 제공한다. 이차 및 3차 반복을 혼합하여 사용하는 것도 가능하다.

적어도 한 번의 2차 반복을 사용하면 오차가 양수, 즉 역수가 과소평가된다.^[13]:370 이는 정확하게 반올림된 몫이 필요한 경우 다음 반올림 단계를 단순화할 수 있다.

초기화나 반복에 더 높은 차수의 다항식을 사용하면 성능 저하가 발생한다. 필요한 추가 곱셈은 더 많은 반복을 수행하는 데 더 잘 사용될 수 있기 때문이다.

골드슈미트 나눗셈

로버트 엘리엇 골드슈미트의 이름을 딴 골드슈미트 나눗셈은^[14][15] 피제수와 제수 모두에 공통 인수 F_i를 반복적으로 곱하여 제수가 1로 수렴하도록 선택하는 반복 과정을 사용한다. 이는 피제수가 구하고자 하는 몫 Q로 수렴하게 한다.

${\displaystyle Q={\frac {N}{D}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots }}{F_{\ldots }}}.}$

골드슈미트 나눗셈의 단계는 다음과 같다.

1. 곱셈 인수 F_i에 대한 추정치를 생성한다.
2. 피제수와 제수에 F_i를 곱한다.
3. 제수가 1에 충분히 가까우면 피제수를 반환하고, 그렇지 않으면 1단계로 돌아간다.

N/D가 0 < D < 1이 되도록 스케일 조정되었다고 가정할 때, 각 F_i는 D를 기반으로 한다.

${\displaystyle F_{i+1}=2-D_{i}.}$

피제수와 제수에 이 인수를 곱하면 다음과 같다.

${\displaystyle {\frac {N_{i+1}}{D_{i+1}}}={\frac {N_{i}}{D_{i}}}{\frac {F_{i+1}}{F_{i+1}}}.}$

충분한 횟수 k의 반복 후 ${\displaystyle Q=N_{k}}$이다.

골드슈미트 방법은 AMD 애슬론 CPU 및 이후 모델에 사용된다.^[16][17] 또한 앤더슨 얼 골드슈미트 파워스(AEGP) 알고리즘으로도 알려져 있으며 다양한 IBM 프로세서에 구현되어 있다.^[18][19] 뉴턴-랩슨 구현과 동일한 속도로 수렴하지만, 골드슈미트 방법의 한 가지 장점은 분자와 분모의 곱셈을 병렬로 수행할 수 있다는 것이다.^[19]

이항 정리

골드슈미트 방법은 이항 정리에 의해 단순화될 수 있는 인수를 사용하여 사용할 수 있다. ${\displaystyle N/D}$가 2의 거듭제곱으로 스케일 조정되어 ${\displaystyle D\in \left({\tfrac {1}{2}},1\right]}$라고 가정하자. 우리는 ${\displaystyle D=1-x}$와 ${\displaystyle F_{i}=1+x^{2^{i}}}$를 선택한다. 이것은 다음을 산출한다.

$${\displaystyle {\frac {N}{1-x}}={\frac {N\cdot (1+x)}{1-x^{2}}}={\frac {N\cdot (1+x)\cdot (1+x^{2})}{1-x^{4}}}=\cdots =Q'={\frac {N'=N\cdot (1+x)\cdot (1+x^{2})\cdot \cdot \cdot (1+x^{2^{(n-1)}})}{D'=1-x^{2^{n}}\approx 1}}}$$.

n 단계(${\displaystyle x\in \left[0,{\tfrac {1}{2}}\right)}$) 후, 분모 ${\displaystyle 1-x^{2^{n}}}$는 상대 오차

${\displaystyle \varepsilon _{n}={\frac {Q'-N'}{Q'}}=x^{2^{n}}}$

로 1로 반올림될 수 있으며, 이는 ${\displaystyle x={\tfrac {1}{2}}}$일 때 ${\displaystyle 2^{-2^{n}}}$에서 최대가 되어 최소 ${\displaystyle 2^{n}}$ 이진 자릿수의 정밀도를 제공한다.

큰 정수 방법

하드웨어 구현을 위해 설계된 방법은 일반적으로 수천 또는 수백만 자리의 십진수를 처리하는 데 적합하지 않다. 이러한 큰 정수는 예를 들어 암호학의 모듈러 축소에서 자주 발생한다. 이러한 큰 정수의 경우, 더 효율적인 호제법은 소수의 곱셈을 사용하도록 문제를 변환하며, 이는 카라추바 알고리즘, 톰-쿡 알고리즘 또는 쇤하게-슈트라센 알고리즘과 같은 점근적으로 효율적인 곱셈 알고리즘을 사용하여 수행할 수 있다. 그 결과, 나눗셈의 계산 복잡도는 곱셈의 복잡도와 동일한 순서(상수 계수까지)를 갖는다. 예로는 위에 설명된 뉴턴 방법에 의한 곱셈으로의 환원,^[20] 약간 더 빠른 버니컬-지글러 나눗셈,^[21] 배럿 축소 및 몽고메리 축소 알고리즘이 포함된다.^{[22][확인 필요]} 뉴턴 방법은 동일한 제수로 여러 번 나누어야 하는 시나리오에서 특히 효율적이다. 초기 뉴턴 역변환 후에는 각 나눗셈에 대해 단 하나의 (절단된) 곱셈만 필요하기 때문이다.

상수로 나누기

상수 D로 나누는 것은 그 역수를 곱하는 것과 같다. 분모는 상수이므로 그 역수(1/D)도 상수이다. 따라서 컴파일 시간에 (1/D)의 값을 한 번 계산하고, 런타임에 N/D 나눗셈 대신 N·(1/D) 곱셈을 수행할 수 있다. 부동소수점 산술에서는 (1/D)를 사용하는 것이 거의 문제가 되지 않지만,^[a] 정수 산술에서는 역수가 항상 0으로 평가된다(|D| > 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와 정확히 동일한 결과를 제공한다. 이는 근사값에 의해 도입된 오차가 시프트 연산에 의해 버려지는 비트에 포함될 만큼 "충분히 가깝기" 때문이다.^[23][24][25] 배럿 축소는 Y 값에 대해 2의 거듭제곱을 사용하여 Y로 나누는 것을 간단한 오른쪽 시프트로 만든다.^[b]

제수 D가 2의 거듭제곱이 아닌 일반적인 x-비트 부호 없는 정수 나눗셈의 경우, 다음 항등식은 나눗셈을 두 번의 x-비트 덧셈/뺄셈, 한 번의 x-비트 곱셈(x-비트 결과의 상위 절반만 사용됨) 및 여러 번의 시프트로 변환한다. 이는 ${\displaystyle k=x+\lceil \log _{2}{D}\rceil }$와 ${\displaystyle a=\left\lceil {\frac {2^{k}}{D}}\right\rceil -2^{x}}$를 미리 계산한 후에 가능하다.

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

어떤 경우에는 "상수 곱셈"을 시프트 및 덧셈 또는 뺄셈의 연속으로 변환하여 상수로 나누는 것을 훨씬 더 짧은 시간 안에 수행할 수 있다.^[27] 특히 10으로 나누는 것이 흥미로운데, 이 경우 나머지가 필요한 경우에도 정확한 몫을 얻을 수 있다.^[28]

반올림 오차

나눗셈 연산을 수행할 때, 정확한 몫 ${\displaystyle q}$와 나머지 ${\displaystyle r}$은 컴퓨터의 정밀도 한계에 맞게 근사된다. 호제법은 다음과 같이 명시한다.

${\displaystyle [a=bq+r]}$

여기서 ${\displaystyle 0\leq r<|b|}$이다.

부동소수점 연산에서 몫 ${\displaystyle q}$는 ${\displaystyle {\tilde {q}}}$로, 나머지 ${\displaystyle r}$은 ${\displaystyle {\tilde {r}}}$로 표현되며, 반올림 오차 ${\displaystyle \epsilon _{q}}$와 ${\displaystyle \epsilon _{r}}$이 발생한다.

${\displaystyle [{\tilde {q}}=q+\epsilon _{q}][{\tilde {r}}=r+\epsilon _{r}]}$

이러한 반올림은 작은 오차를 발생시키며, 이는 후속 계산을 통해 전파되고 누적될 수 있다. 이러한 오차는 반복 과정에서, 그리고 거의 동일한 값을 뺄 때 특히 두드러지며, 이를 유효 숫자 손실이라고 한다. 이러한 오차를 완화하기 위해 가드 숫자 또는 고정밀도 산술과 같은 기술이 사용된다.^[29][30]

 부동소수점 문서에 이 부분의 추가 정보가 있습니다.

같이 보기

• 갈레이 나눗셈
• 곱셈 알고리즘
• 펜티엄 FDIV 버그

참고

1. 이 최적화는 "거의" 문제가 되지 않음에도 불구하고, 현대 컴파일러에서 "빠른 수학" 플래그 뒤에 숨겨져 있는 경우가 많다. 이는 정확하지 않기 때문이다.
2. 현대 컴파일러는 일반적으로 이 정수 곱셈-시프트 최적화를 수행한다. 그러나 런타임에만 알려지는 상수의 경우, 프로그램 자체가 최적화를 구현해야 한다.^[26]

1. 2의 보수가 없는 1의 보수를 사용한 부호 있는 이진 표기법.