Computationally Inequivalent Summations and Their Parenthetic Forms
Preprint
Abstract
Floating-point addition on a finite-precision machine is not associative, so not all mathematically equivalent summations are computationally equivalent. Making this assumption can lead to numerical error in computations. Proper ordering and parenthesizing is a low-overhead way of mitigating such error in a floating point summation. Ordered and parenthesized summations fall into equivalence classes. We describe these classes, and the parenthetic forms summations in these classes take. We provide summation-related interpretations for sequences known in other contexts, and give new recursive and closed formulas for sequences not previously related to summation. We also introduce a data structure that facilitates understanding of these objects, and use it to consider certain forms of summation used by default in widely used computer languages. Finally, we relate this data structure to other mathematical constructs from the fields of mathematical analysis and algorithmic analysis.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Flattening Karatsuba’s Recursion Tree into a Single SummationSN Computer Science, 2019
- Enumeration of lonely pairs of gene trees and species trees by means of antipodal cherriesAdvances in Applied Mathematics, 2018
- The Accuracy of Floating Point SummationSIAM Journal on Scientific Computing, 1993
- The permuted analogues of three Catalan setsJournal of Statistical Planning and Inference, 1993
- What every computer scientist should know about floating-point arithmeticACM Computing Surveys, 1991
- A simple example of the continuous function without derivative1990
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithmsJournal of Computer and System Sciences, 1976