More Web Proxy on the site http://driver.im/

article

Computing machine-efficient polynomial approximations

Authors:

Nicolas Brisebarre,

Jean-Michel Muller,

Arnaud TisserandAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 32, Issue 2

Pages 236 - 256

https://doi.org/10.1145/1141885.1141890

Published: 01 June 2006 Publication History

Abstract

Polynomial approximations are almost always used when implementing functions on a computing system. In most cases, the polynomial that best approximates (for a given distance and in a given interval) a function has coefficients that are not exactly representable with a finite number of bits. And yet, the polynomial approximations that are actually implemented do have coefficients that are represented with a finite---and sometimes small---number of bits. This is due to the finiteness of the floating-point representations (for software implementations), and to the need to have small, hence fast and/or inexpensive, multipliers (for hardware implementations). We then have to consider polynomial approximations for which the degree-i coefficient has at most m_i fractional bits; in other words, it is a rational number with denominator 2^m_i. We provide a general and efficient method for finding the best polynomial approximation under this constraint. Moreover, our method also applies if some other constraints (such as requiring some coefficients to be equal to some predefined constants or minimizing relative error instead of absolute error) are required.

References

[1]

Ancourt, C. and Irigoin, F. 1991. Scanning polyhedra with do loops. In Proceedings of the 3rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP'91). ACM Press, New York, NY, 39--50.

[2]

Borwein, P. and Erdélyi, T. 1995. Polynomials and Polynomials Inequalities. Graduate Texts in Mathematics, 161. Springer-Verlag, New York, NY.

[3]

Collard, J.-F., Feautrier, P., and Risset, T. 1995. Construction of do loops from systems of affine constraints. Parall. Process. Lett. 5, 421--436.

[4]

Cornea, M., Harrison, J., and Tang, P. T. P. 2002. Scientific Computing on Itanium-Based Systems. Intel Press.

[5]

Feautrier, P. 1988. Parametric integer programming. RAIRO Rech. Opér. 22, 3, 243--268.

[6]

Feautrier, P. 2003. PIP/Piplib, a parametric integer linear programming solver. http://www.prism.uvsq.fr/&tilde;cedb/bastools/piplib.html.

[7]

Fox, L. and Parker, I. B. 1972. Chebyshev Polynomials in Numerical Analysis. Oxford Mathematical Handbooks. Oxford University Press, London, UK.

[8]

Granlund, T. 2002. GMP, the GNU multiple precision arithmetic library, version 4.1.2. http:// www.swox.com/gmp/.

[9]

Habsieger, L. and Salvy, B. 1997. On integer Chebyshev polynomials. Math. Computat. 66, 218, 763--770.

[10]

Hart, J. F., Cheney, E. W., Lawson, C. L., Maehly, H. J., Mesztenyi, C. K., Rice, J. R., Thacher, H. G., and Witzgall, C. 1968. Computer Approximations. John Wiley & Sons, New York, NY.

[11]

Le Verge, H., van Dongen, V., and Wilde, D. K. 1994. Loop nest synthesis using the polyhedral library. Tech. Rep. INRIA Research Report RR-2288, (May) INRIA.

[12]

Markstein, P. 2000. IA-64 and Elementary Functions: Speed and Precision. Hewlett-Packard Professional Books. Prentice Hall.

[13]

Muller, J.-M. 1997. Elementary Functions, Algorithms and Implementation. Birkhäuser, Boston, MA.

[14]

Pineiro, J., Bruguera, J., and Muller, J.-M. 2001. Faithful powering computation using table look-up and a fused accumulation tree. In Proceedings of the 15th IEEE Symposium on Computer Arithmetic (Arith-15). Burgess and Ciminiera Eds. IEEE Computer Society Press, Los Alamitos, CA, 40--58.

[15]

Remes, E. 1934. Sur un procédé convergent d'approximations successives pour déterminer les polynômes d'approximation. C.R. Acad. Sci. Paris 198, 2063--2065.

[16]

Rivlin, T. J. 1990. Chebyshev Polynomials. From Approximation Theory to Algebra 2nd Ed. Pure and Applied Mathematics. John Wiley & Sons, New York, NY.

[17]

Schrijver, A. 2003. Combinatorial optimization. Polyhedra and efficiency. Vol. A. Algorithms and Combinatorics, 24. Springer-Verlag, Berlin, Germany.

[18]

Story, S. and Tang, P. T. P. 1999. New algorithms for improved transcendental functions on IA-64. In Proceedings of the 14th IEEE Symposium on Computer Arithmetic. Koren and Kornerup, Eds. IEEE Computer Society Press, Los Alamitos, CA, 4--11.

[19]

Tang, P. T. P. 1989. Table-driven implementation of the exponential function in IEEE floating-point arithmetic. ACM Trans. Math. Soft. 15, 2 (June), 144--157.

[20]

Tang, P. T. P. 1990. Table-driven implementation of the logarithm function in IEEE floating-point arithmetic. ACM Trans. Math. Soft. 16, 4 (Dec.), 378--400.

[21]

Tang, P. T. P. 1991. Table lookup algorithms for elementary functions and their error analysis. In Proceedings of the 10th IEEE Symposium on Computer Arithmetic. P. Kornerup and D. W. Matula, Eds. IEEE Computer Society Press, Los Alamitos, CA, 232--236.

[22]

Tang, P. T. P. 1992. Table-driven implementation of the expm1 function in IEEE floating-point arithmetic. ACM Trans. Math. Soft. 18, 2 (June), 211--222.

[23]

The Polylib Team. 2004. Polylib, a library of polyhedral functions, version 5.20.0. http://icps.u-strasbg.fr/polylib/.

[24]

The Spaces project. 2004. MPFR, the multiple precision floating point reliable library, version 2.0.3. http://www.mpfr.org.

[25]

Wei, B., Cao, J., and Cheng, J. 2001. High-performance architectures for elementary function generation. In Proceedings of the 15th IEEE Symposium on Computer Arithmetic (Arith-15). Burgess and Ciminiera Eds. IEEE Computer Society Press, Los Alamitos, CA, 136--146.

Cited By

Buwono HSugito Alisjahbana SRahayu TTrijeti Alami NPrasiddha HPuspitaningrum D(2024)Effects of Inclination Angle and Height of Blast Load on the Dynamic Behavior of Floor Slabs with Stiffening BeamsCivil and Environmental Engineering10.2478/cee-2024-000620:1(68-77)Online publication date: 26-Jun-2024
https://doi.org/10.2478/cee-2024-0006
Pulido-Gaytan BTchemykh ABabenko MCortés-Mendoza JGonzález-Vélez HAvetisyan A(2024)Enhancing Cloud Security through Efficient Polynomial Approximations for Homomorphic Evaluation of Neural Network Activation Functions2024 IEEE 24th International Symposium on Cluster, Cloud and Internet Computing Workshops (CCGridW)10.1109/CCGridW63211.2024.00011(42-49)Online publication date: 6-May-2024
https://doi.org/10.1109/CCGridW63211.2024.00011
Aanjaneya MNagarakatte SDubach CBruening DHardekopf B(2023)Fast Polynomial Evaluation for Correctly Rounded Elementary Functions using the RLIBM ApproachProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580022(95-107)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3579990.3580022
Show More Cited By

Index Terms

Computing machine-efficient polynomial approximations

Recommendations

Certain classes of polynomial expansions and multiplication formulas

The authors first present a class of expansions in a series of Bernoulli polyomials and then show how this general result can be applied to yield various (known or new) polynomial expansions. The corresponding expansion problem involving the Euler ...
Optimal approximation of the 1/x function using Chebyshev polynomials and magic constants
In this paper we analyze low-cost accurate approximation of the function \(1/x\) using Chebyshev polynomials of the first kind and minimizing number of elementary operations in computer codes (in particular, by using the so called magic constants). It ...
Nonperiodic Trigonometric Polynomial Approximation

The most common approach for approximating non-periodic function defined on a finite interval is based on considering polynomials as basis functions. In this paper we will address the non-optimallity of polynomial approximation and suggest to switch ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 32, Issue 2

June 2006

205 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/1141885

Issue’s Table of Contents

Copyright © 2006 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2006

Published in TOMS Volume 32, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
683
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Buwono HSugito Alisjahbana SRahayu TTrijeti Alami NPrasiddha HPuspitaningrum D(2024)Effects of Inclination Angle and Height of Blast Load on the Dynamic Behavior of Floor Slabs with Stiffening BeamsCivil and Environmental Engineering10.2478/cee-2024-000620:1(68-77)Online publication date: 26-Jun-2024
https://doi.org/10.2478/cee-2024-0006
Pulido-Gaytan BTchemykh ABabenko MCortés-Mendoza JGonzález-Vélez HAvetisyan A(2024)Enhancing Cloud Security through Efficient Polynomial Approximations for Homomorphic Evaluation of Neural Network Activation Functions2024 IEEE 24th International Symposium on Cluster, Cloud and Internet Computing Workshops (CCGridW)10.1109/CCGridW63211.2024.00011(42-49)Online publication date: 6-May-2024
https://doi.org/10.1109/CCGridW63211.2024.00011
Aanjaneya MNagarakatte SDubach CBruening DHardekopf B(2023)Fast Polynomial Evaluation for Correctly Rounded Elementary Functions using the RLIBM ApproachProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580022(95-107)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3579990.3580022
Brisebarre NFilip S(2023) Towards Machine-Efficient Rational L ∞ -Approximations of Mathematical Functions 2023 IEEE 30th Symposium on Computer Arithmetic (ARITH)10.1109/ARITH58626.2023.00029(119-126)Online publication date: 4-Sep-2023
https://doi.org/10.1109/ARITH58626.2023.00029
Bailey D(2023)Computational TechniquesDesign for Embedded Image Processing on FPGAs10.1002/9781119819820.ch5(105-134)Online publication date: 5-Sep-2023
https://doi.org/10.1002/9781119819820.ch5
Hao JXu JGuo SXia Y(2022)Design of variable precision transcendental function automatic generatorThe Journal of Supercomputing10.1007/s11227-021-03937-878:2(2196-2218)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s11227-021-03937-8
Lim JNagarakatte SFreund SYahav E(2021)High performance correctly rounded math libraries for 32-bit floating point representationsProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454049(359-374)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454049
Lim JAanjaneya MGustafson JNagarakatte S(2021)An approach to generate correctly rounded math libraries for new floating point variantsProceedings of the ACM on Programming Languages10.1145/34343105:POPL(1-30)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3434310
Muller J(2020)Elementary Functions and Approximate ComputingProceedings of the IEEE10.1109/JPROC.2020.2991885108:12(2136-2149)Online publication date: Dec-2020
https://doi.org/10.1109/JPROC.2020.2991885
Tumakov D(2019)The Faster Methods for Computing Bessel Functions of the First Kind of an Integer Order with Application to Graphic ProcessorsLobachevskii Journal of Mathematics10.1134/S199508021910028740:10(1725-1738)Online publication date: 18-Oct-2019
https://doi.org/10.1134/S1995080219100287
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents