2 Suma

2Sum to algorytm zmiennoprzecinkowy do obliczania dokładnego błędu zaokrąglenia w operacji dodawania zmiennoprzecinkowego.

2Sum i jego wariant Fast2Sum zostały po raz pierwszy opublikowane przez Møllera w 1965 r. Fast2Sum jest często używany domyślnie w innych algorytmach, takich jak algorytmy sumowania z kompensacją ; Algorytm sumowania Kahana został opublikowany po raz pierwszy w 1965 r., A Fast2Sum został później usunięty z niego przez Dekkera w 1971 r. Dla arytmetycznych typu double-double . Wydaje się, że nazwy 2Sum i Fast2Sum zostały zastosowane wstecznie przez Shewchuka w 1997 roku.

Algorytm

Biorąc pod uwagę dwie liczby zmiennoprzecinkowe i $Displaystyle$ $b}$ , 2Sum oblicza sumę zmiennoprzecinkową ${\ Displaystyle s: = \ operatorname {fl} (a + b)}$ i błąd zmiennoprzecinkowy ${\ Displaystyle t: = a + b- \ operatorname {fl} (a + b)}$ tak, że ${\ displaystyle s + t = a + b}$ . Błąd $.$ w sobie jest liczbą zmiennoprzecinkową

Wprowadza liczby zmiennoprzecinkowe

{\ displaystyle a, b}

Suma wyników

{\ Displaystyle s = \ nazwa operatora {fl} (a + b)}

i błąd

{\ Displaystyle t = a + b -\nazwa operatora {fl} (a+b)}

${\ Displaystyle s: = a \ oplus b}$
${\ Displaystyle a': = s \ ominus b}$
${\ Displaystyle b': = s \ ominus a'}$
${\ Displaystyle \ delta _ {a}: = a \ ominus a'}$
${\ Displaystyle \ delta _ {b}: = b \ ominus b '}$
${\ Displaystyle t: = \ delta _ {a} \ oplus \ delta _ {b}}$
powrót ${\ Displaystyle (s, t)}$

Pod warunkiem, że arytmetyka zmiennoprzecinkowa jest poprawnie zaokrąglana do najbliższej (z powiązaniami rozwiązanymi w dowolny sposób), jak jest to domyślne w IEEE 754 i pod warunkiem, że suma nie przepełnia się, a jeśli jest niedopełniona, zmniejsza się stopniowo , można udowodnić, że ${\ displaystyle s + t = a + b}$ .

Wariant 2Sum o nazwie Fast2Sum wykorzystuje tylko trzy operacje zmiennoprzecinkowe dla arytmetyki zmiennoprzecinkowej na podstawie 2 lub podstawie 3, przy założeniu, że wykładnik $} \displaystyle b}$ co najmniej tak duży, jak wykładnik ${\ Displaystyle a$ , na przykład kiedy ${\ Displaystyle \ lewo | a \ prawo | \ geq \ lewo | b \ prawo |}$ :

Wprowadza

z

zmiennoprzecinkowe radix-2 lub radix-3 ,

displaystyle e_ { a}\geq e_{b}}

co najmniej jeden wynosi zero lub które odpowiednio mają znormalizowane wykładniki mi

za

Suma wyników

{\ Displaystyle s = \ nazwa operatora {fl} (a + b)}

i błąd

{\ Displaystyle t = a + b -\nazwa operatora {fl} (a+b)}

${\ Displaystyle s: = a \ oplus b}$
${\ Displaystyle z = s \ ominus a}$
${\ Displaystyle t = b \ ominus z}$
powrót ${\ Displaystyle (s, t)}$

$algorytmom kompensowanego sumowania$ przybliżenia błędu, tak że , skalarny itp., aby mieć niski błąd, nawet jeśli dane wejściowe nie są posortowane lub tryb zaokrąglania jest nietypowy. Istnieją również bardziej skomplikowane warianty 2Sum i Fast2Sum dla trybów zaokrąglania innych niż zaokrąglanie do najbliższej.

Zobacz też