## Abstract

Given a multiset X = {x_{1},⋯, x_{n}} of real numbers, the floating-point set summation (FPS) problem asks for S_{n} = x_{1} + ··· + x_{n}, and the floating point prefix set summation problem (FPPS) asks for S_{k} = x_{1} + ··· + X_{k} for all k = 1,⋯, n. Let E^{*}_{k} denote the minimum worst-case error over all possible orderings of evaluating Sk-We prove that if X has both positive and negative numbers, it is NP-hard to compute S_{n} with the worst-case error equal to E_{n}. We then give the first known polynomial-time approximation algorithm for computing S_{n} that has a provably small error for arbitrary X. Our algorithm incurs a worstcase error at most 2([log(n - 1)] + 1)E^{*}_{n.}^{1} After X is sorted, it runs in O(n) time, yielding an O(n^{2})-time approximation algorithm for computing S_{k} for all k = 1,⋯, n such that the worst-case error for each Sk is less than 2[log(k - 1)1 + 1)E^{*}_{k}. For the case where X is either all positive or all negative, we give another approximation algorithm for computing S_{n} with a worst-case error at most [log log n]E^{*}_{n}. Even for unsorted X, this algorithm runs in 0(n) time. Previously, the best linear-time approximation algorithm had a worst-case error at most flog n] E_{n}, while E _{n} was known to be attainable in O(n log n) time using Huffman coding. Consequently, FPPS is solvable in O(n^{2}) time such that the worst-case error for each S_{k} is the minimum. To improve this quadratic time bound in practice, we design two on-line algorithms that calculate the next S_{k} by taking advantage of the current S _{k} and thus reduce redundant computation.

Original language | English (US) |
---|---|

Title of host publication | Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings |

Publisher | Springer Verlag |

Pages | 375-386 |

Number of pages | 12 |

ISBN (Print) | 3540647813, 9783540647812 |

DOIs | |

State | Published - 1998 |

Event | 25th International Colloquium on Automata, Languages and Programming, ICALP 1998 - Aalborg, Denmark Duration: Jul 13 1998 → Jul 17 1998 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1443 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 25th International Colloquium on Automata, Languages and Programming, ICALP 1998 |
---|---|

Country/Territory | Denmark |

City | Aalborg |

Period | 7/13/98 → 7/17/98 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)