{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T06:01:49Z","timestamp":1774591309580,"version":"3.50.1"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2006,6,1]],"date-time":"2006-06-01T00:00:00Z","timestamp":1149120000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2006,6]]},"abstract":"<jats:p>\n            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-\n            <jats:italic>i<\/jats:italic>\n            coefficient has at most\n            <jats:italic>m<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            fractional bits; in other words, it is a rational number with denominator 2\n            <jats:sup>\n              <jats:italic>m<\/jats:italic>\n              <jats:sub>\n                <jats:italic>i<\/jats:italic>\n              <\/jats:sub>\n            <\/jats:sup>\n            . 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.\n          <\/jats:p>","DOI":"10.1145\/1141885.1141890","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"236-256","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["Computing machine-efficient polynomial approximations"],"prefix":"10.1145","volume":"32","author":[{"given":"Nicolas","family":"Brisebarre","sequence":"first","affiliation":[{"name":"Universit\u00e9 J. Monnet, St-\u00c9tienne and LIP-E.N.S. Lyon, Lyon Cedex, France"}]},{"given":"Jean-Michel","family":"Muller","sequence":"additional","affiliation":[{"name":"CNRS, LIP-ENS Lyon, Lyon Cedex, France"}]},{"given":"Arnaud","family":"Tisserand","sequence":"additional","affiliation":[{"name":"INRIA, LIP-ENS Lyon, Lyon Cedex, France"}]}],"member":"320","published-online":{"date-parts":[[2006,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 3rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP'91)","author":"Ancourt C.","unstructured":"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. 10.1145\/109625.109631 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. 10.1145\/109625.109631"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Borwein P. and Erd\u00e9lyi T. 1995. Polynomials and Polynomials Inequalities. Graduate Texts in Mathematics 161. Springer-Verlag New York NY.  Borwein P. and Erd\u00e9lyi T. 1995. Polynomials and Polynomials Inequalities. Graduate Texts in Mathematics 161. Springer-Verlag New York NY.","DOI":"10.1007\/978-1-4612-0793-1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1142\/S0129626495000394","article-title":"Construction of do loops from systems of affine constraints","volume":"5","author":"Collard J.-F.","year":"1995","unstructured":"Collard , J.-F. , Feautrier , P. , and Risset , T. 1995 . Construction of do loops from systems of affine constraints . Parall. Process. Lett. 5 , 421 -- 436 . Collard, J.-F., Feautrier, P., and Risset, T. 1995. Construction of do loops from systems of affine constraints. Parall. Process. Lett. 5, 421--436.","journal-title":"Parall. Process. Lett."},{"key":"e_1_2_1_4_1","unstructured":"Cornea M. Harrison J. and Tang P. T. P. 2002. Scientific Computing on Itanium-Based Systems. Intel Press.   Cornea M. Harrison J. and Tang P. T. P. 2002. Scientific Computing on Itanium-Based Systems. Intel Press."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1051\/ro\/1988220302431","article-title":"Parametric integer programming","volume":"22","author":"Feautrier P.","year":"1988","unstructured":"Feautrier , P. 1988 . Parametric integer programming . RAIRO Rech. Op\u00e9r. 22 , 3, 243 -- 268 . Feautrier, P. 1988. Parametric integer programming. RAIRO Rech. Op\u00e9r. 22, 3, 243--268.","journal-title":"RAIRO Rech. Op\u00e9r."},{"key":"e_1_2_1_6_1","unstructured":"Feautrier P. 2003. PIP\/Piplib a parametric integer linear programming solver. http:\/\/www.prism.uvsq.fr\/&tilde;cedb\/bastools\/piplib.html.  Feautrier P. 2003. PIP\/Piplib a parametric integer linear programming solver. http:\/\/www.prism.uvsq.fr\/&tilde;cedb\/bastools\/piplib.html."},{"key":"e_1_2_1_7_1","unstructured":"Fox L. and Parker I. B. 1972. Chebyshev Polynomials in Numerical Analysis. Oxford Mathematical Handbooks. Oxford University Press London UK.  Fox L. and Parker I. B. 1972. Chebyshev Polynomials in Numerical Analysis. Oxford Mathematical Handbooks. Oxford University Press London UK."},{"key":"e_1_2_1_8_1","unstructured":"Granlund T. 2002. GMP the GNU multiple precision arithmetic library version 4.1.2. http:\/\/ www.swox.com\/gmp\/.  Granlund T. 2002. GMP the GNU multiple precision arithmetic library version 4.1.2. http:\/\/ www.swox.com\/gmp\/."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Habsieger L. and Salvy B. 1997. On integer Chebyshev polynomials. Math. Computat. 66 218 763--770. 10.1090\/S0025-5718-97-00829-6   Habsieger L. and Salvy B. 1997. On integer Chebyshev polynomials. Math. Computat. 66 218 763--770. 10.1090\/S0025-5718-97-00829-6","DOI":"10.1090\/S0025-5718-97-00829-6"},{"key":"e_1_2_1_10_1","unstructured":"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.   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."},{"key":"e_1_2_1_11_1","volume-title":"Tech. Rep. INRIA Research Report RR-2288, (May) INRIA.","author":"Le Verge H.","year":"1994","unstructured":"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. 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."},{"key":"e_1_2_1_12_1","volume-title":"IA-64 and Elementary Functions: Speed and Precision","author":"Markstein P.","unstructured":"Markstein , P. 2000. IA-64 and Elementary Functions: Speed and Precision . Hewlett-Packard Professional Books. Prentice Hall . Markstein, P. 2000. IA-64 and Elementary Functions: Speed and Precision. Hewlett-Packard Professional Books. Prentice Hall."},{"key":"e_1_2_1_13_1","volume-title":"Elementary Functions, Algorithms and Implementation","author":"Muller J.-M.","unstructured":"Muller , J.-M. 1997. Elementary Functions, Algorithms and Implementation . Birkh\u00e4user , Boston, MA . Muller, J.-M. 1997. Elementary Functions, Algorithms and Implementation. Birkh\u00e4user, Boston, MA."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 15th IEEE Symposium on Computer Arithmetic (Arith-15)","author":"Pineiro J.","unstructured":"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. 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."},{"key":"e_1_2_1_15_1","first-page":"2063","article-title":"Sur un proc\u00e9d\u00e9 convergent d'approximations successives pour d\u00e9terminer les polyn\u00f4mes d'approximation","volume":"198","author":"Remes E.","year":"1934","unstructured":"Remes , E. 1934 . Sur un proc\u00e9d\u00e9 convergent d'approximations successives pour d\u00e9terminer les polyn\u00f4mes d'approximation . C.R. Acad. Sci. Paris 198 , 2063 -- 2065 . Remes, E. 1934. Sur un proc\u00e9d\u00e9 convergent d'approximations successives pour d\u00e9terminer les polyn\u00f4mes d'approximation. C.R. Acad. Sci. Paris 198, 2063--2065.","journal-title":"C.R. Acad. Sci. Paris"},{"key":"e_1_2_1_16_1","volume-title":"From Approximation Theory to Algebra","author":"Rivlin T. J.","unstructured":"Rivlin , T. J. 1990. Chebyshev Polynomials . From Approximation Theory to Algebra 2 nd Ed. Pure and Applied Mathematics. John Wiley & Sons , New York, NY. Rivlin, T. J. 1990. Chebyshev Polynomials. From Approximation Theory to Algebra 2nd Ed. Pure and Applied Mathematics. John Wiley & Sons, New York, NY.","edition":"2"},{"key":"e_1_2_1_17_1","volume-title":"Combinatorial optimization. Polyhedra and efficiency","author":"Schrijver A.","unstructured":"Schrijver , A. 2003. Combinatorial optimization. Polyhedra and efficiency . Vol. A. Algorithms and Combinatorics, 24 . Springer-Verlag , Berlin, Germany . Schrijver, A. 2003. Combinatorial optimization. Polyhedra and efficiency. Vol. A. Algorithms and Combinatorics, 24. Springer-Verlag, Berlin, Germany."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 14th IEEE Symposium on Computer Arithmetic. Koren and Kornerup, Eds. IEEE Computer Society Press","author":"Story S.","unstructured":"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. 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."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/63522.214389"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/98267.98294"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 10th IEEE Symposium on Computer Arithmetic. P. Kornerup and D. W. Matula, Eds. IEEE Computer Society Press","author":"Tang P. T. P.","year":"1991","unstructured":"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. 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."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/146847.146928"},{"key":"e_1_2_1_23_1","unstructured":"The Polylib Team. 2004. Polylib a library of polyhedral functions version 5.20.0. http:\/\/icps.u-strasbg.fr\/polylib\/.  The Polylib Team. 2004. Polylib a library of polyhedral functions version 5.20.0. http:\/\/icps.u-strasbg.fr\/polylib\/."},{"key":"e_1_2_1_24_1","unstructured":"The Spaces project. 2004. MPFR the multiple precision floating point reliable library version 2.0.3. http:\/\/www.mpfr.org.  The Spaces project. 2004. MPFR the multiple precision floating point reliable library version 2.0.3. http:\/\/www.mpfr.org."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 15th IEEE Symposium on Computer Arithmetic (Arith-15)","author":"Wei B.","unstructured":"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. 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."}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1141885.1141890","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1141885.1141890","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:14:23Z","timestamp":1750259663000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1141885.1141890"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,6]]}},"alternative-id":["10.1145\/1141885.1141890"],"URL":"https:\/\/doi.org\/10.1145\/1141885.1141890","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6]]},"assertion":[{"value":"2006-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}