카한 합계 알고리즘

수치해석에서는 보정 합계라고도 하는 카한 합계 알고리즘이 명백한 접근법에 비해 유한정밀 부동 소수점 시퀀스를 추가하여 얻은 총수의 수치 오차를 유의하게 감소시킨다.^[1] 이는 별도의 실행 보상(작은 오류를 축적하는 변수)을 유지함으로써 이루어지며, 사실상 보상 변수의 정밀도에 의해 총액의 정밀도를 확장한다.

특히 $n{\displaystyle }$ ${\displaystyle n}$을(를) 순차적으로 단순히 $합치면{\displaystyle }$ n$${\$displaystyle$n$\}$에 비례하여 증가하는 최악의 경우 오류가 발생하며, 임의 입력에 $대해$ n ${\$로 증가하는 루트 평균 제곱 오차가 발생한다(반올림 오차는 랜덤워크를 형성함).^[2] 보정된 합계를 사용하면, 충분히 높은 정밀도의 보정 변수를 사용하여 $최악$의 오류 바인딩은 n ${\displaystyle n$과(와) 효과적으로 독립적이므로, 많은 수의 값을 결과의 부동 소수점 정밀도에만 의존하는 오류로 합칠 수 있다.^[2]

이 알고리즘은 윌리엄 카한에 기인한다;^[3] 이보 바부슈카는 독립적으로 유사한 알고리즘을 고안한 것 같다(헨스 카한-바부슈카 합계).^[4] 유사하고 초기 기법은 예를 들어 브레센햄의 라인 알고리즘으로 정수 연산의 누적 오차를 추적한다(동시에^[5] 처음 문서화하기는 했지만). 그리고 델타-시그마 변조.^[6]

알고리즘

유사 코드에서 알고리즘은 다음과 같다.

함수 KahanSum(입력) var sum = 0.0 // 축전지 준비     var c = 0.0 // 손실된 저차 비트에 대한 실행 중인 보상.      i = 1 to input.length do // 배열 입력에는 입력[input.length]에 대한 요소 인덱스 입력[1]이 있다.         var y = 입력[i] - c // c는 처음 0이다.         var t = sum + y // 아아, 합이 크고 y가 작아서 y의 낮은 순서의 숫자가 없어진다. c = (t - sum) - y / (t - sum)는 y의 고차 부분을 취소하고 y를 빼면 마이너스(y의 낮은 부분) sum = t // 대수적으로 c는 항상 0이어야 한다. 지나치게 공격적으로 컴파일러를 최적화하는 것을 조심하라! 다음 i// 다음 번에는 잃어버린 낮은 부분이 새로운 시도로 y에 추가될 것이다.      돈을 돌려주다 

Fast2Sum 알고리즘을 사용하기 위해 이 알고리즘을 다시 쓸 수도 있다.^[7]

함수 KahanSum2(입력) var sum = 0.0 // 축전지 준비     var c = 0.0 // 손실된 저차 비트에 대한 실행 중인 보상.      i = 1 to input.length do // 배열 입력에는 입력[input.length]에 대한 요소 인덱스 입력[1]이 있다.         var y = 입력[i] + c // c는 처음 0이다.         (sum,c) = Fast2Sum(sum,y) // sum + c는 정확한 합에 대한 근사값이다.     다음 i // 다음 번에는 잃어버린 낮은 부분이 새로운 시도로 y에 추가될 것이다.      돈을 돌려주다 

작업 예제

이 예는 십진법으로 제시될 것이다. 컴퓨터는 전형적으로 이진 산수를 사용하지만 도해되고 있는 원리는 같다. 6자리 소수 부동 소수점 산수를 사용한다고 가정합시다. sum 10000.0의 값과 다음 두 개의 값을 얻었다. input[i] 3.14159와 2.71828이다. 정확한 결과는 10005이다.85987, 10005.9로 반올림한다. 평이한 합계로, 각 수신 값은 다음과 같이 정렬될 것이다. sum, 그리고 많은 저차 자릿수가 (잘림 또는 반올림) 손실될 것이다. 라운딩 후 첫 번째 결과는 10003.1이 될 것이다. 두 번째 결과는 라운딩 전 10005.81828, 라운딩 후 10005.8이 될 것이다. 이것은 옳지 않다.

그러나 보정된 합계로 10005.9의 정확한 반올림 결과를 얻는다.

라고 가정하다. c 초기값이 0이다.

  y = 3.14159 - 0.00000 y = 입력[i] - c t = 10000.0 + 3.14159 = 10003.14159 = 6자리만 유지된다.     = 10003.1                       많은 자릿수가 손실되었다! c = (10003.1 - 10000.0) - 3.14159 이것은 반드시 쓰여진 것으로 평가되어야 한다! = 3.10000 - 3.14159 복구된 y의 동화된 부분 대 원래 전체 y. = -0.0415900 후행 0은 6자리 산술이기 때문에 나타난다. 합계 = 10003.1                       따라서 입력(i)에서 소수 자릿수가 합계를 충족하지 않았다.  

합계가 너무 커서 입력 번호의 고차 숫자만 축적되고 있다. 하지만 다음 단계에서는 c 오류를 범하다

  y = 2.71828 - (-0.0415900)        이전 단계의 부족분이 포함된다.     = 2.75987 y와 비슷한 크기: 대부분의 숫자가 만난다. t = 10003.1 + 2.75987 그러나 합을 맞추는 사람은 거의 없다.     = 10005.85987 반올림 = 10005.9                       6자리까지. c = (1천5.9~1천3.1) - 2.75987 이것은 들어간 것을 추출한다. = 2.800~2.75987 이 경우, 너무 많다. = 0.040130. 그러나 어떤 경우에도 초과분은 다음 번에 감산될 것이다. 합계 = 10005.9                       정확한 결과는 10005이다.85987, 이것은 정확히 6자리로 반올림된다.  

따라서 합계는 두 개의 축전지로 수행된다. sum 합계를 가지고 있다, 그리고 c 에 동화되지 않은 부분을 축적하다. sum, 의 저차 부분을 슬쩍 찌르다. sum 다음 번에는 따라서 합계는 다음에서 "보호자 번호"로 진행된다. c는 없는 것보다 낫지만 입력의 두 배의 정밀도로 계산을 수행하는 것만큼 좋지 않다. 그러나 단순히 계산의 정밀도를 높이는 것은 일반적으로 실용적이지 않다. input 이미 정밀도가 2배이고, 4배 정도 정밀도를 제공하는 시스템은 거의 없고, 만약 그렇게 했다면, input 4배 정도 정확할 수 있을 겁니다

정확도

이 섹션은 독자들에게 혼란스럽거나 불명확할 수 있다. 특히 이 절에서는 ε을 사용하는데 반해, 두 가지 상충되는 정의가 존재한다. 나는 대신 너를 사용할 것을 제안한다. 그 정의는 다소 표준적이다. 섹션을 명확히 설명하는 데 도움을 주십시요. 토크 페이지에서 이에 대한 논의가 있을 수 있다. (2021년 12월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

정확도 특성을 평가하기 위해서는 보정 합계 오류에 대한 면밀한 분석이 필요하다. 순진한 합계보다 더 정확하지만, 그것은 여전히 잘못된 조건의 합계에 큰 상대적 오류를 줄 수 있다.

$하나$의 값이 $n{\displaystyle }$ ${\displaystyle n}$의 값 x i ${\displaystyle \{\backslash }$$displaystyle x_{i$ i = 1 , …,${\displaystyle i=1,\,\dots,\,n}$을(를) 합친다고 가정합시다$.$ 정확한 합은 다음과 같다.

${\displaystyle {Sn}_{}}$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{i}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ x ${\displaystyle i_{}}$ ${\$무한정밀도로 환산)

보정된 합계를 사용하면 ${\displaystyle {Sn}_{}}$ +${\displaystyle {}_{}{En}_{}}$ ${\$을(를) 얻을 수 있으며$,$ 여기서 ${\displaystyle {En}_{}}${\$displaystyle E_{n}$은(는) 다음 범위로^[2] 제한된다.

${\displaystyle E_{n} \leq {\big [}2\varepsilon +O(n\varepsilon ^{2}){\big ]}\sum _{i=1}^{n}x_{n},},}$

여기서 ${\displaystyle \varepsilon }$은(는) 채택되는 산술의 기계 정밀도(예: IEEE 표준 이중 정밀 부동소수의 $경우$$\epsilon {\displaystyle }$ ${\displaystyle {10}^{}}$ ${\displaystyle -}$ ${\displaystyle {16}^{}}${\$displaystyle \varepsilon$\ 약 $10^{-16})$이다. 일반적으로 관심의 양은 상대적 오류 ${\displaystyle E_{}}$ n${\displaystyle {}_{}}$/ ${\displaystyle S_{}}$ n $displaystyle E_{n}$/ $S_{n}$ $\},$ 따라서 위에 경계선이 있다.

${\displaystyle {\frac { E_{n} }{ S_{n} }}\leq {\big [}2\varepsilon +O(n\varepsilon ^{2}){\big ]}{\frac {\sum \limits _{i=1}^{n} x_{i} }{\left \sum \limits _{i=1}^{n}x_{i}\right }}.}$

상대 오차범위에 대한 식에서 fraction ${\displaystyle x{}_{}}$ ${\displaystyle i_{}{}_{}}$/ ${\displaystyle \sigma \mathrm{}}$ ${\displaystyle x_{}}$ ${\displaystyle {}_{}}$ $displaystyle \Sigma x_{i}$/ $\Sigma x_{i}}$는 합계$$ 문제의 조건 번호다. 기본적으로 조건 번호는 계산 방법에 관계없이 총계 문제의 오류에 대한 본질적인 민감도를 나타낸다.^[8] 고정밀도(즉 임의정밀 산수를 사용하는 알고리즘이나 데이터에 따라 메모리와 시간 요구사항이 변경되는 알고리즘이 아닌) 고정밀도 알고리즘에 의한 모든 (후방 안정) 합계 방법의 상대 오차범위는 이 조건 번호에 비례한다.^[2] 잘못된 조건의 합계 문제는 이 비율이 큰 문제인데, 이 경우 보상된 합계조차 상대적 오류가 클 수 있다. 예를 들어, 합계 x ${\displaystyle i_{}}$ ${\$가 평균이 0인 비교합 랜덤 번호인 경우 합계는 무작위 보행이며 조건 번호는 $n{\displaystyle \sqrt{}}$ ${\$에 비례하여 증가하게 된다$.$ 반면에 0이 아닌 임의 입력의 경우 조건 번호는 유한 상수로 점증한다.${\displaystyle n}$→ ${\displaystyle \mathrm{\infty }}$ ${\displaystyle n\to \ft$ 입력 내용이 모두 음수가 아닌 경우 조건 번호는 1이다.

조건 번호를 부여하면 보정 합계의 상대적 오차는 $n{\displaystyle }$ ${\displaystyle n$${\displaystyle {}^{}}$과(와) $사실상$ 독립적이다$.$ 원칙적으로 $n{\displaystyle }$ ${\displaystyle n}$과(와) 선형적으로 성장하는$$ $(n\displaystyle N}이)$가 있지만$,$ 실제로 이 용어는 사실상 0이다. 최종 결과는 둥글기 때문이다.ed to 정밀 $\epsilon {\displaystyle }$ ${\displaystyle \varepsilon$ $\},$ $n{\displaystyle }$${\displaystyle {}^{}}$ 2 ${\$ $n}$이(가) 대략$$ $1{\displaystyle \mathrm{}/4}$ $\$ {\$displaystyle 1/\varepsilon }$ 이상인$$ 경우 n ε ${\displaystyle {2\mathrm{}}^{}}$ {\$displaystystylen$ ^{2$}}개$ 항은$$ 0으로 반올림한다.^[2] 두 배의 정밀도로, 이것은 $대부분$의 ${\displaystyle {\mathrm{합}}^{}}$보다 훨씬$$큰 대략 $10$ 16 {\$displaystyle$10$$^{16$}$의 n {\displaystyle $n$$}$에 해당한다. 따라서, 고정 조건 번호의 경우, 보정 합계의 $오류$는$$n {\$displaystyle n}$과(와) 독립적으로$,$ 사실상 $O{\displaystyle }$( ${\displaystyle \epsilon }$) ${\displaystyle$ O$(\varipsilon )}$이다$.$

이에 비해 순진한 합계에 대한 상대적 오차(단순히 숫자를 순서대로 추가, 각 단계에서 반올림)는 O${\displaystyle (}$ $){\displaystyle O(\varepsilon$ n$)}$에 조건 번호를 곱하면서$$ 증가한다.^[2] 그러나 라운딩 오류가 모두 같은 방향에 있을 때만 발생하기 때문에 이 최악의 경우 실전에서 거의 관찰되지 않는다. 실제로 반올림 오류에는 평균이 0인 임의 기호가 있어 무작위 보행을 형성할 가능성이 훨씬 높다. 이 경우 순진한 합계는 $조건{\displaystyle }$ 번호에 O${\displaystyle (}$ $){\$가 곱하여$$ 증가하는 루트 평균 제곱 오차가 있다.^[9] 그러나 이것은 보상된 합계보다 훨씬 더 나쁘다. 그러나 합계를 두 배의 정밀도로 수행할 수 있다면 $if{\displaystyle }$ ${\displaystyle \varepsilon }$을(를) ${\displaystyle {\epsilon \mathrm{}}^{}}$ 2 ${\$ $^{$$2}}$로 대체하고$,$ 순진한 합계는 원래 정밀도로 보정된 합계에서 $O{\displaystyle }$($n { 2$를 가진다$.$

같은 토큰으로, ${\displaystyle {위}_{}}$의 ${\displaystyle {En}_{}}$ ${\$에 나타나는$$ $\sigma {\displaystyle \mathrm{}}$ ${\displaystyle x{}_{}}$ i $displaystyle \Sigma x_{i}$}}은 모든 라운딩 오류가 동일한 기호(그리고 가능한 최대 크기)를 갖는 경우에만 발생하는 최악의 경우 경계다.^[2] $실제로{\displaystyle \mathrm{}}$ ${\displaystyle {sign}_{}}$ x i {\$displaystyle \Sigma x_{i}}}$의 용어는 랜덤워크로 대체되며$$, 이 경우 평균이 0인 임의 입력의 경우에도 ${\displaystyle {오류}_{}}$ E$$n {\$displaystyle E_n}{$$n{\displaystyle \}}$는 O (${\displaystyle \epsilon \sqrt{}}$ n${\displaystyle }$) ${\$)에 따라서만 증가한다$$.$n {\sqrt{n}}($$n{\displaystyle }$ ${\displaystyle {\epsilon \mathrm{}}^{}}$ 2 ${\$기간$$ 무시), $S{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$의 합계 비율이 증가하여$$ 상대 $오류$가 계산될 때 n ${\$요소를$$ 취소한다. 따라서 증상이 없는 조건부 합계의 경우에도 보정 합계에 대한 상대적 오차는 최악의 경우 분석이 시사하는 것보다 훨씬 작을 수 있다.

추가 개선

노이마이어는^[10] 카한 알고리즘의 개선된 버전을 도입했는데, 이를 '향상된 카한-바부슈카 알고리즘'이라고 부르는데, 이 알고리즘은 추가될 다음 용어가 런닝 합계보다 절대값이 클 때도 적용하여 무엇이 크고 무엇이 작은지의 역할을 효과적으로 스와핑하는 것이다. 유사 코드에서 알고리즘은 다음과 같다.

KahanBabushkaNeumaerSum(입력) var sum = 0.0 var c = 0.0 // 손실된 저차 비트에 대한 실행 보상.      i = 1 ~ input.length do t = sum + input[i] = sum >= 입력[i]인 경우 c +=(sum - t) + 입력[i] // 합이 클 경우 입력[i]의 저차 자릿수가 손실된다.         그렇지 않으면 c += (입력[i] - t) + 합 // 그 밖에 저순위의 합이 손실된다.         endif sum = t next i return sum + c // 보정은 맨 마지막에 한 번만 적용되었다.  

이러한 강화는 Fast2Sum으로 다시 작성된 Kahan 알고리즘에서 Fast2Sum by 2Sum을 대체한 것과 유사하다.

많은 수의 숫자에 대해, 두 알고리즘은 일치하지만, 피터스로^[11] 인한 간단한 예는 그것들이 어떻게 다를 수 있는지를 보여준다. $[{\displaystyle 1}$.0${\displaystyle ,}$+ ${\displaystyle {10}^{}}$ ${\displaystyle {100}^{}}$ 1.0${\displaystyle ,}$- ${\displaystyle 10}$ ${\displaystyle {100}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle [1.0,+10^{100,1.0,-10^{100}}}$을(를) 이중 정밀도로 합친$$ 경우 카한의 알고리즘은 0.0을 산출하는 반면, 노이마이어의 알고리즘은 2.0을 산출한다.

더 높은 정확도의 고차 수정도 가능하다. 예를 들어, 클라인이 제안한 변종으로서,^[12] 그는 2차 순서를 "반복적인 카한-바부슈카 알고리즘"이라고 불렀다. 유사 코드에서 알고리즘은 다음과 같다.

기능 KahanBabushkaKleinSum(입력)을 만든다고 합)0.0초본 cs)0.0초본 ccs)0.0을 의미함 c)0.0초본 cc)0.0을 나는 1input.length var 아는 일을 할 정도)합+input[나는]만약 합>)input[나는] 다음 c)(합-t)+input[나는] 다른 c)(input[나는]-t)+합 endif 합)t톤) cs >=c일 경우 cc = (cs - t) + c 다른 cc = (c - t) + cs 엔디프 cs = t ccs = ccs = ccs + cs + cs + cs 

대안

Kahan의 알고리즘이 n개의 숫자를 $합하여{\displaystyle }$O ( ${\displaystyle 1}$) ${\displaystyle$ O$(1)}$오차$$ 증가를 달성하지만, 쌍별 합계에 의해 약간 더 나쁜 $O{\displaystyle }$( ${\displaystyle \mathrm{로그}}$ ${\displaystyle }$ n${\displaystyle }$) ${\displaystyle$ O$(\log$ n$)}$ 증가만$$ 달성할 수 있다. 한 가지는 반복적으로 숫자 집합을 두 반으로 나누어 합한 다음, 두 합을 더한다.^[2] 이는 순진한 합계(산술의 4배, 단순 합계 4배의 지연 시간을 갖는 카한의 알고리즘과 달리)와 동일한 수의 산술 연산을 요구할 수 있는 장점이 있으며 병렬로 계산할 수 있다. 재귀의 기본 사례는 원칙적으로 하나의 (또는 0) 숫자의 합일 수 있지만, 재귀의 오버헤드를 상각하기 위해서는 일반적으로 더 큰 기본 사례를 사용한다. 페어웨이즈 합계의 등가는 많은 빠른 FFT(Fast Fourier Transform) 알고리즘에 사용되며, 그러한 FFT에서 반올림 오류의 로그 증가를 담당한다.^[13] 실제로 랜덤 기호의 반올림 오류와 함께, 쌍별 합계의 루트 평균 제곱 오차는 $실제로{\displaystyle }$ O${\displaystyle (\sqrt{\log }}$ ${\displaystyle \sqrt{n}}$) ${\$만큼 증가한다$.$^[9]

또 다른 대안은 임의의 정밀 산수를 사용하는 것인데, 원칙적으로 훨씬 더 많은 계산 노력을 들인다면 반올림할 필요가 전혀 없다. 임의의 정밀도를 사용하여 정확히 반올림한 합계를 수행하는 방법은 여러 부동소수 성분을 사용하여 적응적으로 확장하는 것이다. 이것은 높은 정밀도가 필요하지 않은 일반적인 경우에서 계산 비용을 최소화할 것이다.^[14][11] 정수 산술만 사용하는 또 다른 방법은 키르치네르와 쿨리쉬가 기술했고,^[15] 하드웨어 구현은 뮐러, 뤼브, 뤼링이 기술했다.^[16]

컴파일러 최적화에 의한 무효화 가능성

원칙적으로, 충분히 공격적으로 최적화한 컴파일러는 카한 요약의 효과를 파괴할 수 있다. 예를 들어, 컴파일러가 실제 산술의 연관성 규칙에 따라 표현을 단순화한다면, 시퀀스의 두 번째 단계를 "간단화"할 수 있다.

t = sum + y;

c = (t - sum) - y;

로

c = ((sum + y) - sum) - y;

그 다음으로는

c = 0;

따라서 오류 보상이 제거된다.^[17] 지 않는 한을 명시적으로 기본적으로associativity-based 변환할 수 있지만 인텔 C++컴파일러 중 하나이다. 예를 들면 컴파일러 옵션"안전하지 않은"optimizations,[18][19][20][21]수 있도록 함으로써 하라는 지시가 실제로, 많은 컴파일러에서는 공동 규칙 단순화에(뿐만 부동 소수 점 연산에서 근사값이다)을 사용하지 않는다.[22] 원래 K&, C프로그래밍 언어의 RC버전은 컴파일러real-arithmetic 공동 규칙에 따라 부동 소수 점 표현 re-order기 위해 C더 수치 응용 프로그램(고 더 포트란, 또한 re-orderin는 것을 금지하는 것과 비슷한 적합할 수 있도록 후속 ANSIC표준 re-ordering 금지했다 허용했다.g)실무에서 컴파일러 옵션은 위에서 언급한 바와 같이 재프로그래밍을 다시 활성화할 수 있다.^[23]

이러한 최적화를 국지적으로 억제하는 휴대용 방법은 원래 공식의 한 줄을 두 개의 문장으로 나누고 중간 제품 중 두 개를 휘발성 있게 만드는 것이다.

함수 KahanSum(입력) var sum = 0.0 var c = 1 ~ input.길이 do var y = 입력[i] - c 휘발성 var t = sum + y 휘발성 var z = t - sum = t - sum = z - y snext i return sum 

라이브러리별 지원

일반적으로 컴퓨터 언어에 내장된 "sum" 함수는 일반적으로 카한 합계는커녕 특정 합계 알고리즘이 사용된다는 보증을 제공하지 않는다.^{[citation needed]} 선형 대수 서브루틴에 대한 BLAS 표준은 성능상의 이유로 특정한 연산 순서를 의무화하는 것을 명백히 피하며,^[24] BLAS 구현은 일반적으로 Kahan 합계를 사용하지 않는다.

파이톤 컴퓨터 언어의 표준 라이브러리는 정확히 반올림된 합계를 위한 fsum 함수를 지정하는데, Shewchuk 알고리즘을^[11] 사용하여 복수의 부분 합계를 추적한다.

줄리아어에서는, 기본 이행법. sum 함수는 높은 정확도와 우수한 성능을 위해 쌍으로 합한 것이지만,^[25] 외부 라이브러리는 Neumaier의 변종인 Neumaier의 구현을 제공한다. sum_kbn 더 높은 정확도가 필요한 경우.^[26]

C# 언어에서 HPCsharp nuget 패키지는 Neumaer 변종 및 쌍별 합계를 구현한다. 스칼라, SIMD 프로세서 지침을 사용한 데이터 병렬, 병렬 멀티코어.^[27]

참고 항목

• 안정적인 합산을 포함하는 분산 계산 알고리즘

참조

외부 링크

• 1996년 9월 Dobb 박사의 저널, 부동소수