Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Sound Compilation of Reals
 
conference paper

Sound Compilation of Reals

Darulova, Eva  
•
Kuncak, Viktor  
2014
POPL 2014
41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL)', u'41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL)

Writing accurate numerical software is hard because of many sources of unavoidable uncertainties, including finite numerical precision of implementations. We present a programming model where the user writes a program in a real-valued implementation and specification language that explicitly includes different types of uncertainties. We then present a compilation algorithm that generates a finite-precision implementation that is guaranteed to meet the desired precision with respect to real numbers. Our compilation performs a number of verification steps for different candidate precisions. It generates verification conditions that treat all sources of uncertainties in a unified way and encode reasoning about finite-precision roundoff errors into reasoning about real numbers. Such verification conditions can be used as a standardized format for verifying the precision and the correctness of numerical programs. Due to their non-linear nature, precise reasoning about these verification conditions remains difficult and cannot be handled using state-of-the art SMT solvers alone. We therefore propose a new procedure that combines exact SMT solving over reals with approximate and sound affine and interval arithmetic. We show that this approach overcomes scalability limitations of SMT solvers while providing improved precision over affine and interval arithmetic. Our implementation gives promising results on several numerical models, including dynamical systems, transcendental functions, and controller implementations.

  • Details
  • Metrics
Type
conference paper
DOI
10.1145/2535838.2535874
Web of Science ID

WOS:000331120500020

Author(s)
Darulova, Eva  
Kuncak, Viktor  
Date Issued

2014

Publisher

ACM

Publisher place

New York

Published in
POPL 2014
Total of pages

14

Start page

235

End page

248

Subjects

roundoff error

•

floating-point arithmetic

•

fixed-point arithmetic

•

verification

•

compilation

•

embedded systems

•

numerical approximation

•

scientific computing

•

sensitivity analysis

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LARA  
Event name
41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL)', u'41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL)
Available on Infoscience
April 2, 2014
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/102491
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés