Complexity measures and hierarchies for the evaluation of integers and polynomials

DOI10.1016/0304-3975(76)90051-7zbMath0365.68049OpenAlexW2056432814MaRDI QIDQ1241288

Richard J. Lipton, David P. Dobkin

Publication date: 1977

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(76)90051-7

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Roundoff error (65G50) Numerical computation of solutions to single equations (65H05)

Related Items (2)

On a generalization of addition chains: addition-multiplication chains ⋮ EFFICIENT GENERATION OF SHORTEST ADDITION-MULTIPLICATION CHAINS

Cites Work

• Unnamed Item
• Unnamed Item
• An Algorithm for the Computation of Linear Forms
• On the Number of Additions to Compute Specific Polynomials
• Polynomials with Rational Coefficients Which are Hard to Compute
• Remarks on number theory III. On addition chains
• On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials

This page was built for publication: Complexity measures and hierarchies for the evaluation of integers and polynomials