skip to main content
10.1145/1141277.1141585acmconferencesArticle/Chapter ViewAbstractPublication PagessacConference Proceedingsconference-collections
Article

Improving the compensated Horner scheme with a fused multiply and add

Published: 23 April 2006 Publication History

Abstract

Several different techniques and softwares intend to improve the accuracy of results computed in a fixed finite precision. Here we focus on a method to improve the accuracy of the polynomial evaluation. It is well known that the use of the Fused Multiply and Add operation available on some microprocessors like Intel Itanium improves slightly the accuracy of the Horner scheme. In this paper, we propose an accurate compensated Horner scheme specially designed to take advantage of the Fused Multiply and Add. We prove that the computed result is as accurate as if computed in twice the working precision. The algorithm we present is fast since it only requires well optimizable floating point operations, performed in the same working precision as the given data.

References

[1]
D. H. Bailey. Algorithm 719, multiprecision translation and execution of Fortran programs. ACM Trans. Math. Software, 19(3):288--319, 1993.
[2]
S. Boldo and J.-M. Muller. Some functions computable with a fused-mac. In IEEE, editor, Proceedings of the 17th IEEE Symposium on Computer Arithmetic, 2005, Cape Cod, Massachusetts, USA. IEEE Computer Society Press, 2005.
[3]
T. J. Dekker. A floating-point technique for extending the available precision. Numer. Math., 18:224--242, 1971.
[4]
S. Graillat, P. Langlois, and N. Louvet. Compensated Horner scheme. Research Report 4, Équipe de recherche DALI, Laboratoire LP2A, Université de Perpignan Via Domitia, France, 52 avenue Paul Alduy, 66860 Perpignan cedex, France, July 2005. Submitted to SIAM J. Sci. Comput.
[5]
S. Graillat, P. Langlois, and N. Louvet. Improving the compensated Horner scheme with a fused multiply and add. Research Report 5, Équipe de recherche DALI, Laboratoire LP2A, Université de Perpignan Via Domitia, France, 52 avenue Paul Alduy, 66860 Perpignan cedex, France, Nov. 2005.
[6]
Y. Hida, X. S. Li, and D. H. Bailey. Algorithms for quad-double precision floating point arithmetic. In N. Burgess and L. Ciminiera, editors, Proceedings of the 15th Symposium on Computer Arithmetic, Vail, Colorado, pages 155--162, Los Alamitos, CA, USA, 2001. Institute of Electrical and Electronics Engineers.
[7]
N. J. Higham. Accuracy and Stability of Numerical Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, second edition, 2002.
[8]
IEEE Standards Committee 754. IEEE Standard for binary floating-point arithmetic, ANSI/IEEE Standard 754--1985. Institute of Electrical and Electronics Engineers, Los Alamitos, CA, USA, 1985. Reprinted in SIGPLAN Notices, 22(2):9--25, 1987.
[9]
D. E. Knuth. The Art of Computer Programming: Seminumerical Algorithms, volume 2. Addison-Wesley, Reading, MA, USA, third edition, 1998.
[10]
The MPFR library. Available at http://www.mpfr.org.
[11]
Y. Nievergelt. Scalar fused multiply-add instructions produce floating-point matrix arithmetic provably accurate to the penultimate digit. ACM Trans. Math. Software, 29(1):27--48, 2003.
[12]
T. Ogita, S. M. Rump, and S. Oishi. Accurate sum and dot product. SIAM J. Sci. Comput., 26(6):1955--1988, 2005.

Cited By

View all
  • (2011)Exact and Approximated Error of the FMAIEEE Transactions on Computers10.1109/TC.2010.13960:2(157-164)Online publication date: 1-Feb-2011
  • (2010)Nonlinear data-bounded polynomial approximations and their applications in ENO methodsNumerical Algorithms10.1007/s11075-010-9395-855:2-3(171-189)Online publication date: 1-Nov-2010
  • (2009)Algorithms for accurate, validated and fast polynomial evaluationJapan Journal of Industrial and Applied Mathematics10.1007/BF0318653126:2-3(191-214)Online publication date: Oct-2009

Index Terms

  1. Improving the compensated Horner scheme with a fused multiply and add

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SAC '06: Proceedings of the 2006 ACM symposium on Applied computing
    April 2006
    1967 pages
    ISBN:1595931082
    DOI:10.1145/1141277
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 23 April 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. IEEE-754 floating point arithmetic
    2. error-free transformations
    3. fused multiply and add
    4. horner scheme
    5. polynomial evaluation

    Qualifiers

    • Article

    Conference

    SAC06
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

    Upcoming Conference

    SAC '25
    The 40th ACM/SIGAPP Symposium on Applied Computing
    March 31 - April 4, 2025
    Catania , Italy

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)7
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 17 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2011)Exact and Approximated Error of the FMAIEEE Transactions on Computers10.1109/TC.2010.13960:2(157-164)Online publication date: 1-Feb-2011
    • (2010)Nonlinear data-bounded polynomial approximations and their applications in ENO methodsNumerical Algorithms10.1007/s11075-010-9395-855:2-3(171-189)Online publication date: 1-Nov-2010
    • (2009)Algorithms for accurate, validated and fast polynomial evaluationJapan Journal of Industrial and Applied Mathematics10.1007/BF0318653126:2-3(191-214)Online publication date: Oct-2009

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media