×
Lipton, Richard J.; Dobkin, David

Complexity measures and hierarchies for the evaluation of integers and polynomials. (English) Zbl 0365.68049

Theor. Comput. Sci. 3(1976), 349-357 (1977).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0365.68049

Cited in 2 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity
65G50 Roundoff error
65H05 Numerical computation of solutions to single equations
Cite Review PDF
Full Text: DOI

References:

[1] Brauer, A., Bull. Amer. Math. Soc., 45, 736-739 (1939) · JFM 65.0154.02
[2] Borodin, A.; Cook, S., On the number of additions to compute specific polynomials, SIAM J. Comput, 5, 146-157 (1976) · Zbl 0341.65034
[3] S. Cook, Linear time simulation of deterministic two-way push-down automata, Proc. IFIP Congr. 71, TA-2; S. Cook, Linear time simulation of deterministic two-way push-down automata, Proc. IFIP Congr. 71, TA-2
[4] Erdös, P., Acta Arith, 6, 77-81 (1960) · Zbl 0219.10064
[5] Knuth, D., The Art of Computer Programming, Volume II: Seminumerical Algorithms (1969), Addison-Wesley: Addison-Wesley Massachusetts · Zbl 0191.18001
[6] Landau, E., Über einige neuere Fortschritte der additiven Zahlentheorie (1937), Cambridge University Press · JFM 63.0129.02
[7] Niven, I.; Zuckerman, H., An Introduction to the Theory of Numbers (1972), Wiley: Wiley NY · Zbl 0237.10001
[8] Paterson, M. S.; Stockmeyer, L. J., On the number of nonscalar multiplications necessary to evaluate polynomials, SIAM J. Comput., 2, 60-66 (1973) · Zbl 0262.65033
[9] Savage, J., An algorithm for the computation of linear forms, SIAM J. Comput., 3, 150-158 (1974) · Zbl 0291.68015
[10] Strassen, V., Polynomials with rational coefficients which are hard to compute, SIAM J. Comput., 3, 128-149 (1974) · Zbl 0289.68018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.