2섬

2Sum은^[1] 부동 소수점 추가 작업에서 정확한 반올림 오류를 계산하기 위한 부동 소수점 알고리즘이다.

2Sum과 그것의 변종 Fast2Sum은 Möller에 의해 1965년에 처음 출판되었다.^[2]Fast2Sum은 종종 보상 합계 알고리즘과 같은 다른 알고리즘에서 암묵적으로 사용된다.^[1] Kahan의 Summation 알고리즘은 1965년에 처음 출판되었고 ^[3]Fast2Sum은 이후 Decker에 의해 이중 이중 산술 알고리즘에 대해 1971년에 인수되었다.^[4]2Sum과 Fast2Sum이라는 이름은 1997년 Shewchuk에 의해 소급 적용되었던 것으로 보인다.^[5]

알고리즘.

Given two floating-point numbers ${\displaystyle a}$ and ${\displaystyle b}$, 2Sum computes the floating-point sum ${\displaystyle s:=\operatorname {fl} (a+b)}$ and the floating-point error ${\displaystyle t:=a+b-\operatorname {fl} (a+b)}$ so that ${\disp$$레이스타일 s$$t=a+b}$오류 $t{\displaystyle }$ ${\displaystyle t}$은(는) 그 자체가 부동 소수점 숫자다$$.

${\displaystyle \mathrm{부동}}$ 소수점 번호 $a{\displaystyle }$, b ${\displaystyle a,b}$ 입력

출력 합계 $s{\displaystyle }$= ${\displaystyle \mathrm{fl}}$ ${\displaystyle }$(${\displaystyle }$+ ${\displaystyle b}$) ${\displaystyle$ s$=\operatorname {fl}($${\displaystyle a}$$+b)}$ 및$$ 오류 $t{\displaystyle }$= ${\displaystyle a}$+${\displaystyle b}$)${\displaysty t=a+b-\operatorname {fl}(a+b)}$

1. ${\displaystyle s:=a\oplus b}$
2. $(\displaystyle a:displaystyle a:=s\minus b}$
3. $(\displaystyle b':=s\sominus a'}$
4. $\displaystyle \cHB _{a}=a\inus a'}$
5. $\displaystyle \pair _{b:=b\minus b'}$
6. ${\displaystyle t:=\filename _{a}\oplus \b}}$
7. 반환$({\displaystyle s}$, ${\displaystyle t}$) ${\displaystyle(s,t)}$

부동 소수점 산술이 IEEE 754의 기본값과 같이 가장 가까운 값(어떤 방법으로든 해결된 동점)으로 정확하게 반올림되고, 합계가 넘치지 않고, 과소 흐름일 경우,${\displaystyle }s{\displaystyle }$ +${\displaystyle t}$ = ${\displaystyle a}$ =${\displaystyle }$a + ${\displaystyle b}$ = + b$[\displaysty s+t=a+b}$라는 것을 증명할 수 있다$.$^[1][6][2]

Fast2Sum이라고 하는 2Sum의 변형은 ${\displaystyle \ge }$ ${\displaystyle b}$ ${\$\left $b\rie$}의 지수가 적어도$$ $b{\displaystyle }$ ${\displaystyle b$의 지수만큼 크다는 가정 하에 radix 2 또는 radix 3의 부동소수 연산만을 사용한다.$ght }$^[1][6][7][4]:

입력 radix-2 또는 radix-3 부동 소수점 $}$과 b ${\displaystyle$a}$$및 b {\$displaystyle b}$중 하나 이상이 0이거나 각각${\displaystyle {}_{}{a}_{}}$ e ${\$에 정규화된 지수를 갖는 숫자

출력 합계 $s{\displaystyle }$= ${\displaystyle \mathrm{fl}}$ ${\displaystyle }$(${\displaystyle }$+ ${\displaystyle b}$) ${\displaystyle$ s$=\operatorname {fl}($${\displaystyle a}$$+b)}$ 및$$ 오류 $t{\displaystyle }$= ${\displaystyle a}$+${\displaystyle b}$)${\displaysty t=a+b-\operatorname {fl}(a+b)}$

1. ${\displaystyle s:=a\oplus b}$
2. $(\디스플레이 스타일 z=s\minus a})$
3. $t=b\minus z}$
4. 반환$({\displaystyle s}$, ${\displaystyle t}$) ${\displaystyle(s,t)}$

조건이 충족되지 않더라도 2Sum과 Fast2Sum은 ${\displaystyle \mathrm{종종}}$ ${\displaystyle \mathrm{오류}}$에 대한 합리적인 근사를 제공하여 s${\displaystyle }$+ ${\displaystyle t}$ ${\displaystyle \approx }$ a product a + b ${\displaystyle s+t\$약$a+b$을(를) 통해 보정 합계, 도트-product 등에 대한 알고리즘이 가능하므로 입력이 정렬되지 않거나 라운딩 모드가 비정상적이더라도 오류가 낮을 수 있다.^[1][2]2Sum과 Fast2Sum의 더 복잡한 변형은 라운드 투 니어티 이외의 라운딩 모드에서도 존재한다.^[1]

참고 항목

• 카한 합계 알고리즘
• 반올림 오차
• 더블더블산술

참조