Exact real arithmetic with perturbation analysis and proof of correctness

S. Keshishzadeh, J.F. Groote

Onderzoeksoutput: Boek/rapportRapportAcademic

34 Downloads (Pure)

Samenvatting

In this article, we consider a simple representation for real numbers and propose top-down procedures to approximate various algebraic and transcendental operations with arbitrary precision. Detailed algorithms and proofs are provided to guarantee the correctness of the approximations. Moreover, we develop and apply a perturbation analysis method to show that our approximation procedures only recompute expressions when unavoidable. In the last decade, various theories have been developed and implemented to realize real computations with arbitrary precision. Proof of correctness for existing approaches typically consider basic algebraic operations, whereas detailed arguments about transcendental operations are not available. Another important observation is that in each approach some expressions might require iterative computations to guarantee the desired precision. However, no formal reasoning is provided to prove that such iterative calculations are essential in the approximation procedures. In our approximations of real functions, we explicitly relate the precision of the inputs to the guaranteed precision of the output, provide full proofs and a precise analysis of the necessity of iterations.
Originele taal-2Engels
Plaats van productieEindhoven
UitgeverijTechnische Universiteit Eindhoven
Aantal pagina's58
StatusGepubliceerd - 2015

Publicatie series

NaamComputer science reports
Volume1505
ISSN van geprinte versie0926-4515

Vingerafdruk Duik in de onderzoeksthema's van 'Exact real arithmetic with perturbation analysis and proof of correctness'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Keshishzadeh, S., & Groote, J. F. (2015). Exact real arithmetic with perturbation analysis and proof of correctness. (Computer science reports; Vol. 1505). Technische Universiteit Eindhoven.