×

Evaluating rational functions: Infinite precision is finite cost and tractable on average. (English) Zbl 0622.68038

The main issue of the paper is the loss of precision in evaluating a rational function P/Q. The authors show that though in general it can be arbitrarily large, on the average the loss is finite and even small. The paper deserves special attention not only because of the main result and its application to approximating the loss of significance for solving systems of linear equations. It convincingly advocates extension of the notion ”tractable” to mean ”polynomial time computable on the average”, and the methods from geometric measure theory and integral geometry employed in the paper break-through the standard complexity theory paradigm.
Reviewer: M.Chytil

MSC:

68Q25 Analysis of algorithms and problem complexity
65G99 Error analysis and interval analysis
26C15 Real rational functions
28A75 Length, area, volume, other geometric measure theory
PDFBibTeX XMLCite
Full Text: DOI Link