2Suma

2Sum ^{[ 1 ]} es un algoritmo de punto flotante para calcular el error de redondeo exacto en una operación de suma de punto flotante.

2Sum y su variante Fast2Sum fueron publicados por primera vez por Ole Møller en 1965. ^{[ 2 ]} Fast2Sum se usa a menudo implícitamente en otros algoritmos, como los algoritmos de suma compensada ; ^{[ 1 ]} el algoritmo de suma de Kahan se publicó por primera vez en 1965, ^{[ 3 ]} y Fast2Sum fue posteriormente factorizado por Dekker en 1971 para algoritmos de aritmética doble-doble . ^{[ 4 ]} Los nombres 2Sum y Fast2Sum parecen haber sido aplicados retroactivamente por Shewchuk en 1997. ^{[ 5 ]}

Dados dos números de punto flotante${\displaystyle a}$y${\displaystyle b}$, 2Sum calcula la suma de punto flotante${\displaystyle s:=a\oplus b}$redondeado al más cercano y el error de punto flotante${\displaystyle t:=a+b-(a\oplus b)}$de modo que${\displaystyle s+t=a+b}$, dónde${\displaystyle \oplus }$y${\displaystyle \ominus }$denotan respectivamente la suma y la resta redondeadas al más cercano. El error${\displaystyle t}$es en sí mismo un número de punto flotante.

Introduce números de punto flotante${\displaystyle a,b}$

Salida suma redondeada${\displaystyle s=a\oplus b}$y error exacto${\displaystyle t=a+b-(a\oplus b)}$

1. ${\displaystyle s:=a\oplus b}$
2. ${\displaystyle a':=s\ominus b}$
3. ${\displaystyle b':=s\ominus a'}$
4. ${\displaystyle \delta _{a}:=a\ominus a'}$
5. ${\displaystyle \delta _{b}:=b\ominus b'}$
6. ${\displaystyle t:=\delta _{a}\oplus \delta _{b}}$
7. devolver${\displaystyle (s,t)}$

Siempre que la aritmética de punto flotante se redondee correctamente al más cercano (con los empates resueltos de cualquier manera), como es el valor predeterminado en IEEE 754 , y siempre que la suma no se desborde y, si se desborda, se desborde gradualmente , se puede demostrar que${\displaystyle s+t=a+b}$. ^{[ 1 ] [ 6 ] [ 2 ]}

Una variante de 2Sum llamada Fast2Sum utiliza solo tres operaciones de punto flotante, para aritmética de punto flotante en base 2 o base 3, bajo el supuesto de que el exponente de${\displaystyle a}$es al menos tan grande como el exponente de${\displaystyle b}$, como cuando${\displaystyle \left|a\right|\geq \left|b\right|}$: ^{[ 1 ] [ 6 ] [ 7 ] [ 4 ]}

Introduce números de coma flotante de base 2 o base 3.${\displaystyle a}$y${\displaystyle b}$donde al menos uno es cero, o que tienen exponentes normalizados${\displaystyle e_{a}\geq e_{b}}$

Salida suma redondeada${\displaystyle s=a\oplus b}$y error exacto${\displaystyle t=a+b-(a\oplus b)}$

1. ${\displaystyle s:=a\oplus b}$
2. ${\displaystyle z=s\ominus a}$
3. ${\displaystyle t=b\ominus z}$
4. devolver${\displaystyle (s,t)}$

Aunque no se cumplan las condiciones, 2Sum y Fast2Sum suelen proporcionar aproximaciones razonables al error, es decir${\displaystyle s+t\approx a+b}$, lo que permite que los algoritmos para la suma compensada, el producto escalar, etc., tengan un error bajo incluso si las entradas no están ordenadas o el modo de redondeo es inusual. ^{[ 1 ] [ 2 ]}

Se utilizan variantes más complejas de 2Sum y Fast2Sum para modos de redondeo distintos del redondeo al más cercano. ^{[ 1 ]}

• Algoritmo de suma de Kahan
• Error de redondeo
• aritmética doble-doble