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 Møller en 1965. [2] Fast2Sum se usa a menudo implícitamente en otros algoritmos como los de suma compensada ; [1] El algoritmo de suma de Kahan se publicó por primera vez en 1965, [3] y Fast2Sum más tarde fue descartado por Dekker en 1971 para algoritmos aritméticos doble-doble . [4] Los nombres 2Sum y Fast2Sum parecen haber sido aplicados retroactivamente por Shewchuk en 1997. [5]
Algoritmo
Dados dos números de coma flotante y , 2Sum calcula la suma de punto flotante y el error de coma flotante así que eso . El error es en sí mismo un número de punto flotante.
- Ingresa números de punto flotante
- Suma de salidas y error
- regreso
Siempre que la aritmética de punto flotante esté correctamente redondeada al más cercano (con empates resueltos de cualquier manera), como es el valor predeterminado en IEEE 754 , y siempre que la suma no se desborde y, si se desborde, se desborde gradualmente , se puede probar que. [1] [6] [2]
Una variante de 2Sum llamada Fast2Sum usa 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 es al menos tan grande como el exponente de , como cuando : [1] [6] [7] [4]
- Entradas radix-2 o números de punto flotante radix-3 y , de los cuales al menos uno es cero, o que respectivamente tienen exponentes normalizados
- Suma de salidas y error
- regreso
Incluso si no se cumplen las condiciones, 2Sum y Fast2Sum a menudo proporcionan aproximaciones razonables al error de modo que , que permite que los algoritmos de suma compensada, producto escalar, etc. tengan un error bajo incluso si las entradas no están ordenadas o el modo de redondeo es inusual. [1] [2] También existen variantes más complicadas de 2Sum y Fast2Sum para modos de redondeo distintos al redondeo al más cercano. [1]
Ver también
Referencias
- ↑ a b c d e f Muller, Jean-Michel; Brunie, Nicolas; de Dinechin, Florent; Jeannerod, Claude-Pierre; Joldes, Mioara; Lefèvre, Vincent; Melquiond, Guillaume; Revol, Nathalie; Torres, Serge (2018). Manual de aritmética de coma flotante (2ª ed.). Cham, Suiza: Birkhäuser. págs. 104-111. doi : 10.1007 / 978-3-319-76526-6 . ISBN 978-3-319-76525-9.
- ^ a b c Møller, Ole (marzo de 1965). "Cuasi doble precisión en la suma de punto flotante". BIT Matemáticas numéricas . 5 : 37–50. doi : 10.1007 / BF01975722 . S2CID 119991676 .
- ^ Kahan, W. (enero de 1965). "Más comentarios sobre la reducción de errores de truncamiento". Comunicaciones de la ACM . Asociación para Maquinaria de Computación. 8 (1): 40. doi : 10.1145 / 363707.363723 . ISSN 0001-0782 . S2CID 22584810 .
- ^ a b Dekker, TJ (junio de 1971). "Una técnica de punto flotante para ampliar la precisión disponible" . Numerische Mathematik . 18 (3): 224–242. doi : 10.1007 / BF01397083 . S2CID 63218464 .
- ^ Shewchuk, Jonathan Richard (octubre de 1997). "Aritmética de punto flotante de precisión adaptativa y predicados geométricos robustos rápidos" . Geometría discreta y computacional . 18 (3): 305–363. doi : 10.1007 / PL00009321 .
- ^ a b Knuth, Donald E. (1998). El arte de la programación informática, Volumen II: Algoritmos seminuméricos (3ª ed.). Addison – Wesley. pag. 236. ISBN 978-0-201-89684-8.
- ^ Sterbenz, Pat H. (1974). Computación en coma flotante . Englewood Cliffs, Nueva Jersey, Estados Unidos: Prentice-Hall. págs. 138-143. ISBN 0-13-322495-3.