나눗셈 알고리즘

분할 알고리즘은 두 개의 정수 N과 D(각각 분자와 분모)가 주어지면 유클리드 분할의 결과인 몫 및/또는 나머지를 계산하는 알고리즘입니다.어떤 것들은 수작업으로 적용되는 반면, 다른 것들은 디지털 회로 설계와 소프트웨어로 사용됩니다.

분할 알고리즘은 느린 분할과 빠른 분할의 두 가지 주요 범주로 나뉩니다.느린 분할 알고리즘은 반복당 최종 몫의 한 자리를 만듭니다.느린 분할의 예로는 복원, 미수행 복원, 미복원, SRT 분할 등이 있습니다.빠른 분할 방법은 최종 몫에 근접한 근사치로 시작하여 각 반복에서 최종 몫의 두 배의 자릿수를 생성합니다.^[1]뉴턴-라프슨 및 골드슈미트 알고리즘이 이 범주에 속합니다.

이러한 알고리즘의 변형을 통해 빠른 곱셈 알고리즘을 사용할 수 있습니다.결과적으로 큰 정수의 경우 분할에 필요한 컴퓨터 시간은 곱셈에 필요한 시간과 일정한 계수까지 같으며 곱셈 알고리즘을 사용하는 경우에도 마찬가지입니다.

이 논의는 $양식{\displaystyle N}$/D${\displaystyle }$=${\displaystyle }$(${\displaystyle Q,}$R$)$ {\$displaystyle$N/D = $(Q$,R$)}$을 참조하며$,$ 여기서

• N = 분자(배당)
• D = 분모(분모)

는 입력이고,

• Q = 몫
• R = 나머지

는 출력입니다.

뺄셈 반복에 의한 나눗셈

역사적으로 유클리드의 요소인 제7권 명제 1에 제시된 가장 큰 공약수 알고리즘에 통합된 가장 간단한 분할 알고리즘은 뺄셈과 비교만을 사용하여 두 개의 양의 정수가 주어진 나머지를 찾습니다.

R := N Q := 0 하는 동안에 R ≥ D 하다   R := R − D   Q := Q + 1 끝. 돌아가다 (Q,R) 

몫과 나머지가 존재하고 고유하다는 증명(유클리드 나눗셈에서 설명)은 덧셈, 뺄셈, 비교를 사용하여 음수와 양수 모두에 적용할 수 있는 완전한 나눗셈 알고리즘을 생성합니다.

기능. 나누다(N, D)   한다면 D = 0 그리고나서 오류를(0별 구분) 끝.   한다면 D < 0 그리고나서 (Q, R) := 나누다(N, −D); 돌아가다 (−Q, R) 끝.   한다면 N < 0 그리고나서     (Q,R) := 나누다(−N, D)     한다면 R = 0 그리고나서 돌아가다 (−Q, 0)     또 다른 돌아가다 (−Q − 1, D − R) 끝.   끝.   -- 이때 N ≥ 0, D > 0   돌아가다 분할_부호(N, D) 끝.   기능. 분할_부호(N, D)   Q := 0; R := N   하는 동안에 R ≥ D 하다     Q := Q + 1     R := R − D   끝.   돌아가다 (Q, R) 끝. 

이 절차는 항상 R ≥ 0을 생성합니다. 매우 간단하지만 ω(Q) 단계를 거치기 때문에 long division과 같은 느린 분할 알고리즘보다도 기하급수적으로 느립니다.Q가 작다고 알려져 있고(출력에 민감한 알고리즘), 실행 가능한 사양으로 사용할 수 있는 경우 유용합니다.

장구분

긴 나눗셈은 십진법으로 표현된 여러 자리 숫자를 펜과 종이로 나누는 데 사용되는 표준 알고리즘입니다.배당의 왼쪽 끝에서 오른쪽 끝으로 점진적으로 이동하여 각 단계에서 (숫자 수준에서) 나눗셈의 가장 큰 배수를 뺀 다음 배수가 몫의 자릿수가 되고, 마지막 차이는 나머지가 됩니다.

이진 래딕스와 함께 사용하면 아래의 나머지 알고리즘과 함께 (부호화되지 않은) 정수 분할의 기초가 됩니다.짧은 나눗셈은 한 자리 나눗셈에 적합한 긴 나눗셈의 축약형입니다.부분계수법 또는 행맨법으로도 알려진 청킹은 이해하기 더 쉬울 수 있는 덜 효율적인 형태의 긴 분할입니다.각 단계에서 현재 가지고 있는 것보다 더 많은 배수를 뺄 수 있게 함으로써, 더 자유로운 형태의 긴 분할 변형도 개발될 수 있습니다.

나머지가 있는 정수 분할(부호 없음)

다음 알고리즘인 유명한 긴 분할의 이진법은 N을 D로 나누고 몫을 Q에 두고 나머지를 R에 둡니다.다음 의사 코드에서는 모든 값이 부호 없는 정수로 처리됩니다.

한다면 D = 0 그리고나서 오류를(Division by Zero Exception) 끝. Q := 0                  -- 몫과 나머지를 0으로 초기화 R := 0                      위해서 i := n − 1 .. 0 하다  -- 여기서 n은 N의 비트 수입니다.   R := R << 1           -- 좌변속 R(1비트   R(0) := N(i)          -- R의 최하위 비트를 분자의 비트 i와 동일하게 설정합니다.   한다면 R ≥ D 그리고나서     R := R − D     Q(i) := 1   끝. 끝. 

예

N= 1100 (12) 및 D= 100 (4)을 취할 경우

1단계: R=0 및 Q=0 설정
2단계: i=3 (N의 비트 수보다 1개 작음)을 취합니다.
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.

완분법

느린 분할 방법은 모두 표준 재발 방정식에 기초합니다.

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

여기서:

• R은_j 분할의 j번째 부분 나머지입니다.
• B는 기수(베이스, 일반적으로 컴퓨터와 계산기의 내부적으로 2개)입니다.
• q는 n-(j+1) 위치에 있는 몫의 자릿수이며, 여기서 자릿수 위치는 최소 signific수 0부터 최대 n-1까지 번호가 매겨집니다.
• n은 몫의 자릿수입니다.
• D는 나눗셈기

분할복원중

복원 나눗셈은 고정 소수점에 따라 작동하며 가정 0 < D < N에 따라 달라집니다.^{[citation needed]}

몫 자리 q는 자리 집합 {0,1}에서 형성됩니다.

이진(라딕스 2) 복원 분할의 기본 알고리즘은 다음과 같습니다.

R := N D := D << n            -- R과 D는 N과 Q의 두배의 단어 폭이 필요합니다. 위해서 i := n − 1 .. 0 하다  -- 예를 들어 32비트의 경우 31.0   R := 2 * R − D          -- 이동된 값에서 시도적 감산(2 곱하기는 이진 표현의 이동)   한다면 R >= 0 그리고나서     q(i) := 1          -- 결과-비트 1   또 다른     q(i) := 0          -- 결과-비트 0     R := R + D         -- 새 부분 나머지가 (복원) 이동값입니다.   끝. 끝.  -- 여기서 N = 분자, D = 분모, n = #bit, R = 부분 나머지, q(i) = 몫의 비트 #i 

미수행 복원 나눗셈은 2R의 값이 저장된다는 점을 제외하면 나눗셈 복원과 유사하므로 R < 0인 경우에는 D를 다시 추가할 필요가 없습니다.

비복원분할

복원하지 않는 분할에서는 몫 자릿수에 {0, 1} 대신 숫자 집합 {-1, 1}을(를) 사용합니다.알고리즘은 더 복잡하지만 하드웨어로 구현할 경우 의사결정과 몫 비트당 덧셈/ 뺄셈이 하나밖에 없다는 장점이 있습니다. ^[3]뺄셈 후에는 복원 단계가 없으므로 연산 수가 최대 절반으로 줄어들고 더 빠르게 실행할 수 있습니다.^[4]음이 아닌 숫자의 이진법 (라딕스 2) 비복원 분할에 대한 기본 알고리즘은 다음과 같습니다.

R := N D := D << n            -- R과 D는 N과 Q의 두배의 단어 폭이 필요합니다. 위해서 i = n − 1 .. 0 하다  -- 예를 들어, 32비트의 경우 31.0.   한다면 R >= 0 그리고나서     q(i) := +1     R := 2 * R − D   또 다른     q(i) := −1     R := 2 * R + D   끝. 한다면 끝.   -- 참고:N= numer레이터, D= denomin레이터, n=#비트, R= partial 나머지, q(i)=비트 #i의 몫. 

이 알고리즘에 따라 몫은 -1과 +1의 숫자로 구성된 비표준 형태입니다.이 양식은 최종 몫을 구성하려면 이진법으로 변환해야 합니다.예:

다음 몫을 숫자 집합 {0,1}로 변환합니다.
시작:	${\displaystyle Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}$
1. 양의 항을 형성합니다.	${\displaystyle P=11101010\,}$
2. 음의 항을 마스킹*:	${\displaystyle M=00010101\,}$
3. 뺄셈: ${\displaystyle P}$- M ${\displaystyle P-M$	${\displaystyle Q=11010101\,}$
*.(2의 보어 없이 자신의 보어로 부호화된 이진 표기법)

$Q{\displaystyle }$ ${\displaystyle$ Q$}$의 -1자리가 일반적으로 0(0$$)으로 저장되어 있으면 $P{\displaystyle }${\$displaystyle P}$는 Q$${\$displaystyle$ Q$}$이고 $M{\displaystyle }${\$displaystyle M}$ 계산은 사소한$$ 것입니다. 원래 $Q{\displaystyle }$ ${\displaystyle Q}$에 대한 보어(비트 단위 보어)를 수행합니다$.$

Q := Q − 조금.빈둥빈둥(Q)      -- Q의 -1자리를 일반적으로 0으로 표시할 경우 적절합니다. 

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

한다면 R < 0 그리고나서   Q := Q − 1   R := R + D  -- 나머지가 관심있는 경우에만 필요합니다. 끝. 한다면 

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

SRT사업부

SRT 분할은 많은 마이크로프로세서 구현에서 분할에 널리 사용되는 방법입니다.^[5][6]알고리즘의 이름은 D에서 따온 것입니다.IBM의 W. 스위니, 제임스 E.일리노이 대학교 로버트슨과 K. D. 임페리얼 컬리지 런던의 토처.이들은 모두 거의 동시에 알고리즘을 독자적으로 개발했습니다(1957년 2월, 1958년 9월, 1958년 1월에 각각 발표).^[7][8][9]

SRT 분할은 비복원 분할과 유사하지만 배당금 및 분할자를 기반으로 한 조회표를 사용하여 각 몫 자릿수를 결정합니다.

가장 중요한 차이점은 중복 표현이 몫에 사용된다는 것입니다.예를 들어 radix-4 SRT 분할을 구현할 때 각 몫 자리는 {-2, -1, 0, +1, +2}의 다섯 가지 가능성 중에서 선택됩니다.따라서 몫자리의 선택이 완벽할 필요는 없습니다. 나중의 몫자리는 약간의 오류를 수정할 수 있습니다. (예를 들어 몫자리 쌍 (0, +2)과 (1, -2)는 0x4+2 = 1x4-2이므로 동치입니다.)이 허용 오차를 사용하면 전폭 뺄셈을 필요로 하지 않고, 배당과 나눗셈의 가장 중요한 비트 몇 개만 사용하여 몫 자릿수를 선택할 수 있습니다.이렇게 단순화하면 2보다 높은 기수를 사용할 수 있습니다.

비복원 분할과 마찬가지로 마지막 단계는 마지막 몫 비트를 해결하는 최종 전폭 감산과 몫을 표준 이진 형태로 변환하는 것입니다.

인텔 펜티엄 프로세서의 악명 높은 부동 소수점 분할 버그는 잘못된 코드화된 룩업 테이블로 인해 발생했습니다.1066개의 출품작 중 5개가 실수로 누락되었습니다.^[10][11]

속분할법

뉴턴-라프슨 분할

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

뉴턴-라프슨 분할 단계는 다음과 같습니다.

1. $D{\displaystyle }$ ${\displaystyle D}$의 역수 $1{\displaystyle \mathrm{}/D}$ ${\displaystyle 1/D}$에 대한$$ 견적 $X{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$을 계산합니다$.$
2. 연속적으로 더 정확한 $추정치$를 계산합니다. 역수의 ${\displaystyle {X1\mathrm{}}_{}}$${\displaystyle {}_{}}$ ${\displaystyle {X2\mathrm{}}_{}}$ ${\displaystyle \dots ,}$ ${\displaystyle {XS}_{}}$ ${\$여기서 뉴턴-라프슨 방법을 사용합니다.
3. 배당금에 약수의 역수를 곱하여 몫을 계산합니다. $Q$ = ${\displaystyle N}$ ${\displaystyle {}_{}}$ ${\displaystyle S_{}}$ ${\displaystyle$Q = $NX_{S$

뉴턴 방법을 적용하여 $D$ ${\displaystyle D}$의 역수를 구하려면$$$X$${\displaystyle }$= ${\displaystyle 1}$ /${\displaystyle D}$ ${\displaystyle$X = 1 / $D}$에 영이 있는 함수 ${\displaystyle f}$ ($X{\displaystyle )}$ ${\displaystyle$f$(X)}$를 찾아야 합니다$.$ 명백한 이러한 함수는 f ${\displaystyle (X)}$ = ${\displaystyle \mathrm{D}}$ ${\displaystyle X}$- 1 ${\displaystyle f(X$) = dx-1$}$이지만$$이에 대한 뉴턴-라프슨 반복은 c가 될 수 없으므로 도움이 되지 않습니다.$D{\displaystyle }$ ${\displaystyle D}$의 역수를 이미 알지 못한 상태에서 계산됩니다($$게다가 반복적인 개선을 허용하는 대신 한 단계에서 정확한 역수를 계산하려고 시도합니다).작용하는 함수는 $f$ (${\displaystyle X)}$ = ${\displaystyle (1}$/ ${\displaystyle X}$)${\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 {Xi}_{}}$ ${\$에서 곱셈과 뺄셈만 사용하거나$$ 두 개의 융합 곱셈을 사용하여 계산할 수 있습니다.

계산 관점에서 식 ${\displaystyle {Xi}_{}}$+ ${\displaystyle 1_{}}$ = ${\displaystyle {Xi}_{}}$+ ${\displaystyle {Xi}_{}}$(${\displaystyle 1}$- ${\displaystyle D}$ ${\displaystyle {Xi}_{}}$ ${\displaystyle X_{i+1$} = $X_{i}$ + $X_{i}($1 - DX_${i})}$ 및 ${\displaystyle {Xi}_{}}$+ ${\displaystyle 1_{}}$ = ${\displaystyle {Xi}_{}}$(${\displaystyle 2}$ -${\displaystyle D}$ ${\displaystyle {Xi}_{}}$ ${\displaystyle X_{i+1$} = $X_{i}($2 - DX_${i})}$은(는) 동등하지 않습니다.두 번째 표현식을 사용하면서 2n비트의 정밀도로 결과를 ${\displaystyle {얻으려면}_{}}$ Xi$${\$displaystyle$X_{$i}$와 (${\displaystyle 2_{}}$ -${\displaystyle }$D${\displaystyle {}_{}}$xi$)$ {\$displaystyle$ (2 - D X_{$i})}$ 사이의$$곱을 $Xi$ {\$displaystyle$$$X_${i$n비트)의 두 배로$$ 계산해야 합니다.^{[citation needed]}반대로 ${\displaystyle {Xi}_{}}$ ${\$와 $({\displaystyle 1}$- ${\displaystyle D}$ ${\displaystyle {xi}_{}}${\$displaystyle$(1 - D X_${i})}$ 사이의 곱은 $({\displaystyle 1}$- ${\displaystyle D}$ ${\displaystyle {xi}_{}}$ ${\displaystyle$(1 - D X_${i})}$의 n비트(이진점 뒤)가$$ 0이므로 n비트의 정밀도로만 계산하면 됩니다$$.

오류가 ε ${\displaystyle i_{}}$ = ${\displaystyle 1}$ -${\displaystyle D}$ ${\displaystyle X_{}}$ i ${\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}}$

각 반복 단계에서의 오차 제곱, 즉 뉴턴-라프슨 방법의 이른바 2차 수렴은 모든 반복에 대해 결과의 정확한 자릿수가 대략 두 배로 증가하는 효과를 갖는데, 이 특성은 관련된 숫자가 많은 숫자를 가질 때(예: 큰 정수 영역에서) 매우 가치 있게 됩니다.그러나 이는 또한 초기 추정치 $X{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$이(가) 잘못 선택된 경우 방법의 초기 수렴이 상대적으로 느려질 수 있음을 의미합니다.

초기 추정치 $X{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$을 선택하는 하위 문제의 경우$,$ 0.5 ≤ D ≤ 1이 되도록 수의 D에 비트 시프트를 적용하는 것이 편리합니다. 분자 N에 동일한 비트 시프트를 적용함으로써, 몫이 변하지 않도록 보장합니다.그러면 한 사람은 그 형태로 선형 근사를 사용할 수 있습니다.

${\displaystyle X_{0}=T_{1}+T_{2}D\근접 {\frac {1}{D}}\,}$

뉴튼-라프슨을 초기화합니다.구간${\displaystyle }$[${\displaystyle 0.5,}$ ${\displaystyle 1]}$ ${\displaystyle [0.5,1$] {\displaystyle [0.5,1$]}$에서 오차의 절대값의 최대값을 최소화하려면 다음을 사용해야 합니다$.$

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

선형 근사의 계수는 다음과 같이 결정됩니다.오류의 절대값은 ε ${\displaystyle 0_{}}$ = ${\displaystyle 1}$ -${\displaystyle }$D ${\displaystyle ({}_{}}$ ${\displaystyle 1_{}}$+ T ${\displaystyle 2_{}}$ ${\displaystyle {}_{}}$) $displaystyle \varepsilon _{0}$ = 1 - $D (T_{1}$ + $T_{2$)입니다.$}D)$ $\}.$ 오차의 최대 절대값의 최소값은 F${\displaystyle (D)}$ $=$ $1$ -${\displaystyle D}$ ${\displaystyle ({}_{}}$ ${\displaystyle 1_{}}$+ T ${\displaystyle 2_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle$ F$(D)$ $=$ 1 - D $(T_{1}$ + $T_{2$)에 적용된 체비셰프 등각 정리에 의해 결정됩니다.$}D$ F${\displaystyle \text{'}(D)}$ {\$displaystyle$ F$(D)}$의 로컬 최소값은 F${\displaystyle \text{'}(D)}$ $=$${\displaystyle }$$0 {\displaystyle$ F$'(D)$$=$$0}$일$$때 $발생$하며, $이$ 값은 솔루션 D $=$$$- ${\displaystyle T_{}}$ 1${\displaystyle }$/ (${\displaystyle {2T}_{}}$ 2${\displaystyle {}_{}}${\$displaystyle$ D$=$-$T_{1}/(2T_{2}}$입니다$.$해당 최소값의 함수는 끝점의 함수로서 반대 부호여야 합니다$.$ 즉, $F{\displaystyle (1/2)}$ = -${\displaystyle F(}$- ${\displaystyle {}_{}}$ ${\displaystyle 1_{}}$/${\displaystyle }$( ${\displaystyle 2}$ ${\displaystyle {}_{}}$ ${\displaystyle 2_{}}$)${\displaystyle F(1/2$) =$F(1$) = $-F(-T_{1}/(2T_{2})}.$두 미지수에 있는 두 방정식은 T 1 = ${\displaystyle 48}$ ${\displaystyle /}$ ${\displaystyle 17}$ ${\displaystyle T_{1$} = $48/17}$와 T ${\displaystyle 2_{}}$ = - ${\displaystyle 32}$ ${\displaystyle /}$ ${\displaystyle 17}${\$displaystyle T_{2$} =$-32/17$}이며$,$ 최대 오차는 $F$ (${\displaystyle 1)}$= ${\displaystyle 1}$/ ${\displaystyle 17}$ ${\displaystyle F(1$) = $1/17}$입니다$.$ 이 근사치를 사용하면 초기값의 오차의 절대값은 다음보다 작습니다.

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

Remez 알고리즘을 사용하여 계수를 계산하여 1보다 큰 차수의 다항식 적합을 생성할 수 있습니다.절충점은 초기의 추측이 더 많은 계산 사이클을 필요로 하지만 뉴턴-라프슨의 반복 횟수를 줄이는 대신 가능하기를 바란다는 것입니다.

이 방법의 수렴은 정확히 2차이므로 다음과 같습니다.

${\displaystyle S=\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}$

단계는 최대 $P{\displaystyle }$ ${\$개의$$ 이진 자리까지 값을 계산하기에 충분합니다.이는 IEEE 단일 정밀도의 경우 3, 이중 정밀도와 이중 확장 형식 모두의 경우 4로 평가됩니다.

의사코드

다음은 다음의 몫을 계산합니다.N그리고.D정도의 정밀하게P이진 위치:

1 ≤ M < 2 (표준 부동 소수점 표현) D' := D / 2 // 스케일 0.5와 1 사이에서 비트 시프트 / 지수 감산 N' := N / 2 X : = 48/17 - 32/17 × D' // 계산 상수를 D 반복 ⌈ ${\displaystyle {\mathrm{로그}}_{}}$ ${\displaystyle 2_{}}$ ⁡ ${\displaystyle P\frac{}{}}$+ 1 ${\displaystyle \frac{{\mathrm{로그}}_{}}{}}$ ${\displaystyle \frac{2_{}}{}}$ ⁡ ${\displaystyle \frac{17}{}}$ ⌉ $displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _2}$$17}}\right\rceil \,}$회 // 고정 PX 기준으로 사전 계산 가능 :$=$ X + X × (1 - D' × X) 종료 반환 N' × X

예를 들어, 이중 정밀 부동 소수점 분할의 경우 이 방법은 10배수, 9추가 및 2교대를 사용합니다.

변형 뉴턴-라프슨 분열

뉴턴-라프슨 분할 방법은 다음과 같이 약간 더 빠르게 수정할 수 있습니다.D가 [0.5, 1.0]이 되도록 N과 D를 이동시킨 후, 다음과 같이 초기화합니다.

${\displaystyle X:={\frac {140}{33}}+D\cdot \left ({\frac {-64}{11}}+D\cdot {\frac {256}{99}\right).}$

이는 1/D에 대한 최적의 2차 적합치이며 오차의 절대값을 1/99 이하로 제공합니다.오차를 제1 종류의 재스케일링된 3차 체비셰프 다항식과 동일하게 만들기 위해 선택됩니다.계수는 사전에 계산되고 하드 코딩되어야 합니다.

그런 다음 루프에서 오차를 세제곱하는 반복을 사용합니다.

${\displaystyle E:=1-D\cdot X}$

${\displaystyle Y:=X\cdot E}$

${\displaystyle X:=X+Y+Y\cdot E.}$

Y·E 용어는 새것입니다.

X가 선행 P 비트에서 1/D와 일치할 때까지 루프를 수행하면 반복 횟수는 다음과 같습니다.

${\displaystyle \left\lceil \log _{3}\left({\frac {P+1}{\log _{2}99}}\right)\rceil }$

이는^P+1 2에 도달하기 위해 99를 세제곱해야 하는 횟수입니다.그리고나서

${\displaystyle Q:=N\cdot X}$

는 P비트에 대한 몫입니다.

초기화 또는 반복에서 더 높은 차수의 다항식을 사용하면 더 많은 반복을 수행하는 데 필요한 추가 곱셈이 더 효과적이기 때문에 성능이 저하됩니다.

골드슈미트 사단

Goldschmidt^[12] 분할(로버트 엘리엇 골드슈미트 이후)^[13]은 분배와 분배 모두에_i 공통 인자 F를 반복적으로 곱하는 반복 과정을 사용하며, 이를 통해 분배가 1로 수렴되도록 선택합니다.이로 인해 배당금이 구하고자 하는 몫 Q로 수렴하게 됩니다.

${\displaystyle Q={\frac {N}{D}}{\frac {F_{1}}{{F_{1}}{\frac {F_{2}}}{\frac {F_{\ldots}}{F_{\ldots}}{{\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}}{\frac {F_{i+1}}{F_{i+1}}}.$

k번의 충분한 반복 후 $Q{\displaystyle }$= ${\displaystyle {Nk}_{}}$ ${\displaystyle$ Q = $N_{k$

골드슈미트 방법은 AMD 애슬론 CPU 및 이후 모델에 사용됩니다.^[14][15]AEGP(Anderson Earle Goldschmidt Powers) 알고리즘으로도 알려져 있으며 다양한 IBM 프로세서에 의해 구현됩니다.^[16][17]뉴턴-라프슨 구현과 동일한 속도로 수렴하지만, 골드슈미트 방법의 한 가지 장점은 분자와 분모의 곱셈을 병렬로 수행할 수 있다는 것입니다.^[17]

이항 정리

Goldschmidt 방법은 이항 정리에 의한 단순화를 허용하는 요인과 함께 사용될 수 있습니다.$N$ /${\displaystyle D}$ ${\displaystyle N/D}$이(가) $D{\displaystyle }$∈$($ ${\displaystyle 1]}$ ${\displaystyle D\in \left$ ({\$tfrac {1}{2}}, 1\right]}$의 거듭제곱으로 ${\displaystyle {스케일링}_{}}$되었다고 가정합니다$.$ ${\displaystyle \mathrm{D}}$ = 1 -${\displaystyle x}$ ${\displaystyle D$=$1-x$$}$을(를) $선택$하고${\displaystyle {Fi}^{}}$ = ${\displaystyle {1^{}}^{}}$+ x 2 i {\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}}=\cdot =Q'={\frac {N'=N\cdot(1+x)\cdot(1+x^{2})\cdot \cdot \cdot(1+x^{n-1}}}{D'=1-x^{2^{n}}\약 1}}$$

.

n단계$({\displaystyle x}$ ∈${\displaystyle }$[ ${\displaystyle 0,}$ ${\displaystyle \frac{12}{}}$)${\displaystyle \left(x\in \left[0,{\tfrac {1}{2}}\right)}\right)}}$후$$분모 $1$ -${\displaystyle }$x ${\displaystyle 2^{}}$ ${\displaystyle {n^{}}^{}}$ ${\displaystyle$1 - x$^{2^{n}}$를 1로 반올림할 수 있으며 상대적인 오차가 있습니다.

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

$x$ = ${\displaystyle \frac{12}{}}$ ${\displaystyle$x = {\$tfrac {1}{2}}$일 때 2 - ${\displaystyle {2^{}}^{}}$ n${\displaystyle 2^{n}}$에서 최대이므로 2 n ${\displaystyle 2^{n}$의 이진수의 최소 $정밀도$를 제공합니다$.$

대정수법

하드웨어 구현을 위해 설계된 방법은 일반적으로 몇 천 또는 몇 백만 개의 십진 숫자를 가진 정수로 확장되지 않습니다. 예를 들어, 암호학의 모듈식 감소에서 이러한 방법이 자주 발생합니다.이러한 큰 정수에 대해 보다 효율적인 분할 알고리즘은 적은 수의 곱셈을 사용하도록 문제를 변환시키며, 이는 Karatsuba 알고리즘, Tom-Cook 곱셈 또는 Schönhage-Strassen 알고리즘과 같은 점근적으로 효율적인 곱셈 알고리즘을 사용하여 수행할 수 있습니다.결과적으로 분할의 계산 복잡도는 곱셈의 계산 복잡도와 같은 차수(최대 곱셈 상수)입니다.위에서 설명한 뉴턴 방법에 의한 곱셈으로의 축소뿐만 아니라 약간 ^[18]더 빠른 버니켈-지글러 분할,^[19] 바렛 축소 및 몽고메리 축소 알고리즘 등이 그 예입니다.^{[20][verification needed]}뉴턴의 방법은 초기 뉴턴 반전 후 각 분할마다 한 번의 (절단된) 곱셈만 필요하기 때문에 동일한 분할로 여러 번 분할해야 하는 시나리오에서 특히 효율적입니다.

상수로 나눗셈

상수 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는 존재하지 않습니다.다행히 (N·X)/Y는 정수 산술에서 N/D와 정확히 동일한 결과를 제공하지만 (X/Y)가 1/D와 정확히 동일하지는 않지만 근사치에 의해 도입된 오류가 시프트 연산에 의해 폐기되는 비트에 있을 정도로 충분히 가깝습니다.^[21][22][23]바렛 감소는 Y 값에 대해 2의 거듭제곱을 사용하여 Y에 의한 분할을 단순한 우변위로 만듭니다.^[b]

구체적인 고정 소수점 산술 예로서 32비트 부호 없는 정수의 경우 3으로 나눈 값을 곱한 값으로 바꿀 수 있습니다. 2863311531/2³³, 곱하기 2863311531 (16진수 0xAAA)AAAAB)에 이어 33개의 오른쪽 비트 시프트.2863311531의 값은 2³³/3으로 계산된 다음 반올림됩니다.마찬가지로, 10으로 나누는 것은 3435973837 (0xCCCCCCD)에 의해 곱셈으로 표현되고 이어서 2 (또는³⁵ 35 오른쪽 비트 시프트)에 의해 나눗셈으로 표현될 수 있습니다.^{[25]: p230-234} OEIS는 곱셈에 대해 A346495로 그리고 오른쪽 시프트에 대해 A34649로 상수 시퀀스를 제공합니다.

나눗셈 D가 2의 거듭제곱이 아닌 일반적인 x비트 비부호 정수 나눗셈의 경우, 다음 항등식은 나눗셈을 2개의 x비트 덧셈/감산, 1개의 x비트는 x비트 곱셈(결과의 상반만 사용되는 경우) 및 여러 번의 시프트로 변환하고,${\displaystyle \mathrm{사전}}$ 계산${\displaystyle }$k = x + ⁡ ${\displaystyle {로그}_{}}$ 2 ⌉ ${\displaystyle D}$ ⌈ {\$displaystyle$ k$$= x+\$lceil$ \$log _{2}{$D}\$rceil }$ 및 $a$ = ⌈ ${\displaystyle \frac{2^{}}{}}$ ${\displaystyle \frac{{}^{}}{}}$ D${\displaystyle }$⌉ - ${\displaystyle 2^{}}$x {\$displaystyle$ a =\$left$\${\frac {$2^{k$}}{D}\right\rceil -2^{x}$:

${\displaystyle \left\l floor {\frac {N}{D}}\right\rfloor =\left\loor {\frac {N-b}{2}}\right\rfloor +b}{2^{k-x-1}}\right\rfloor {\text{where}}b=\left\loor {\frac {Na}{2^{x}}\right\rfloor }$

어떤 경우에는 "상수 곱하기"^[26]를 일련의 시프트로 변환하여 더 적은 시간 내에 상수로 분할할 수 있습니다.특히 관심있는 것은 정확한 몫을 얻는 10으로 나누는 것이고, 필요한 경우 나머지를 얻는 것입니다.^[27]

반올림오류

이 섹션은 확장이 필요합니다.추가하면 도움이 됩니다. (2012년 9월)

반올림 오차는 정밀도가 제한적이기 때문에 분할 작업에 의해 발생할 수 있습니다.

참고 항목

• 갤리 디비전
• 곱셈 알고리즘
• 펜티엄 FDIV 버그

메모들

참고문헌

추가열람

• Savard, John J. G. (2018) [2006]. "Advanced Arithmetic Techniques". quadibloc. Archived from the original on 2018-07-03. Retrieved 2018-07-16.