Optimal bounds for floating-point addition in constant time

Mak Andrlon, Peter Schachte, Harald Sondergaard, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

Reasoning about floating-point numbers is notoriously difficult, owing to the lack of convenient algebraic properties such as associativity. This poses a substantial challenge for program analysis and verification tools which rely on precise floating-point constraint solving. Currently, interval methods in this domain often exhibit slow convergence even on simple examples. We present a new theorem supporting efficient computation of exact bounds of the intersection of a rectangle with the preimage of an interval under floating-point addition, in any radix or rounding mode. We thus give an efficient method of deducing optimal bounds on the components of an addition, solving the convergence problem.

Original languageEnglish
Title of host publicationProceedings - 26th IEEE Symposium on Computer Arithmetic, ARITH-26 (2019)
EditorsNaofumi Takagi, Sylvie Boldo, Martin Langhammer
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages159-166
Number of pages8
ISBN (Electronic)9781728133669
ISBN (Print)9781728133676
DOIs
Publication statusPublished - 2019
EventIEEE Symposium on Computer Arithmetic 2019 - Kyoto, Japan
Duration: 10 Jun 201912 Jun 2019
Conference number: 26th
http://www.lab3.kuis.kyoto-u.ac.jp/arith26/

Conference

ConferenceIEEE Symposium on Computer Arithmetic 2019
Abbreviated titleARITH 2019
CountryJapan
CityKyoto
Period10/06/1912/06/19
Internet address

Keywords

  • addition
  • arbitrary radix
  • bound analysis
  • floating point arithmetic

Cite this

Andrlon, M., Schachte, P., Sondergaard, H., & Stuckey, P. J. (2019). Optimal bounds for floating-point addition in constant time. In N. Takagi, S. Boldo, & M. Langhammer (Eds.), Proceedings - 26th IEEE Symposium on Computer Arithmetic, ARITH-26 (2019) (pp. 159-166). [8877445] IEEE, Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ARITH.2019.00038