Correct rounding of algebraic functions

Nicolas Brisebarre; Jean-Michel Muller

RAIRO - Theoretical Informatics and Applications (2007)

  • Volume: 41, Issue: 1, page 71-83
  • ISSN: 0988-3754

Abstract

top
We explicit the link between the computer arithmetic problem of providing correctly rounded algebraic functions and some diophantine approximation issues. This allows to get bounds on the accuracy with which intermediate calculations must be performed to correctly round these functions.

How to cite

top

Brisebarre, Nicolas, and Muller, Jean-Michel. "Correct rounding of algebraic functions." RAIRO - Theoretical Informatics and Applications 41.1 (2007): 71-83. <http://eudml.org/doc/250075>.

@article{Brisebarre2007,
abstract = { We explicit the link between the computer arithmetic problem of providing correctly rounded algebraic functions and some diophantine approximation issues. This allows to get bounds on the accuracy with which intermediate calculations must be performed to correctly round these functions. },
author = {Brisebarre, Nicolas, Muller, Jean-Michel},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Floating-point arithmetic; computer arithmetic; algebraic functions; correct rounding; diophantine approximation.},
language = {eng},
month = {4},
number = {1},
pages = {71-83},
publisher = {EDP Sciences},
title = {Correct rounding of algebraic functions},
url = {http://eudml.org/doc/250075},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Brisebarre, Nicolas
AU - Muller, Jean-Michel
TI - Correct rounding of algebraic functions
JO - RAIRO - Theoretical Informatics and Applications
DA - 2007/4//
PB - EDP Sciences
VL - 41
IS - 1
SP - 71
EP - 83
AB - We explicit the link between the computer arithmetic problem of providing correctly rounded algebraic functions and some diophantine approximation issues. This allows to get bounds on the accuracy with which intermediate calculations must be performed to correctly round these functions.
LA - eng
KW - Floating-point arithmetic; computer arithmetic; algebraic functions; correct rounding; diophantine approximation.
UR - http://eudml.org/doc/250075
ER -

References

top
  1. American National Standards Institute and Institute of Electrical and Electronic Engineers. IEEE standard for binary floating-point arithmetic. ANSI/IEEE Standard, Std 754-1985, New York (1985).  
  2. N.P. Brousentsov, S.P. Maslov, J. Ramil Alvarez and E.A. Zhogolev, Development of ternary computers at Moscow State University. Technical report, Dept. VMK MGU (2000). Available at .  URIhttp://www.computer-museum.ru/english/setun.htm
  3. W.J. Cody, A proposed radix and word length independent standard for floating-point arithmetic. ACM SIGNUM Newsletter20 (1985) 37–51.  
  4. W.J. Cody, J.T. Coonen, D.M. Gay, K. Hanson, D. Hough, W. Kahan, R. Karpinski, J. Palmer, F.N. Ris and D. Stevenson, A proposed radix-and-word-length-independent standard for floating-point arithmetic. IEEE MICRO4 (1984) 86–100.  
  5. E. Croot, R.-C. Li, and H.J. Zhu, The abc conjecture and correctly rounded reciprocal square roots. Theor. Comput. Sci.315 (2004) 405–417.  
  6. C.B. Dunham, Feasibility of “perfect” function evaluation. SIGNUM Newsletter25 (1990) 25–26.  
  7. S. Gal and B. Bachelis, An accurate elementary mathematical library for the IEEE floating point standard. ACM Trans. Math. Software17 (1991) 26–45.  
  8. A. Hurwitz, Über die angenäherte Darstellung der Irrationalzahlen durch rationale Brüche. Math. Ann.46 (1891) 279–284.  
  9. American National Standards Institute, Institute of Electrical, and Electronic Engineers. IEEE standard for radix independent floating-point arithmetic. ANSI/IEEE Standard, Std 854-1987, New York (1987).  
  10. C. Iordache and D.W. Matula, On infinitely precise rounding for division, square root, reciprocal and square root reciprocal, in Proceedings of the 14th IEEE Symposium on Computer Arithmetic (Adelaide, Australia), edited by Koren and Kornerup, IEEE Computer Society Press, Los Alamitos, CA (1999) 233–240.  
  11. A.Ya. Khintchine, Continued fractions. Translated by Peter Wynn. P. Noordhoff Ltd., Groningen (1963).  
  12. T. Lang and J.-M. Muller, Bound on runs of zeros and ones for algebraic functions, in Proc. of the 15th IEEE Symposium on Computer Arithmetic (Arith-15), edited by Burgess and Ciminiera, IEEE Computer Society Press (2001).  
  13. V. Lefèvre, Moyens arithmétiques pour un calcul fiable. Thèse, École normale supérieure de Lyon, Lyon, France (2000).  
  14. V. Lefèvre and J.-M. Muller, Worst cases for correct rounding of the elementary functions in double precision, in Proc. of the 15th IEEE Symposium on Computer Arithmetic (Arith-15), edited by Burgess and Ciminiera, IEEE Computer Society Press (2001).  
  15. A.-M. Legendre, Essai sur la théorie des nombres. Duprat, Paris, An VI (1798).  
  16. J. Liouville, Nouvelle démonstration d'un théorème sur les irrationnelles algébriques inséré dans le compte rendu de la dernière séance. C.R. Acad. Sci. Paris, Sér. A18 (1844) 910–911.  
  17. J. Liouville, Sur des classes très étendues de quantités dont la valeur n'est ni algébrique, ni même réductible à des irrationnelles algébriques. C.R. Acad. Sci. Paris, Sér. A18 (1844) 883–885.  
  18. J. Liouville, Sur des classes très étendues de quantités dont la valeur n'est ni algébrique, ni même réductible à des irrationnelles algébriques. J. Math. Pures Appl.16 (1851) 133–142.  
  19. K.F. Roth, Rational approximations to algebraic numbers. Mathematika2 (1955) 1–20; corrigendum 168 (1955).  
  20. D. Stehlé, V. Lefèvre and P. Zimmermann, Searching worst cases of a one-variable function using lattice reduction. IEEE Trans. Comput.54 (2005) 340–346.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.