×
Rabin, Michael O.; Winograd, Shmuel

Fast evaluation of polynomials by rational preparation. (English) Zbl 0238.12002

Commun. Pure Appl. Math. 25, 433-458 (1972).
It is well known that by calculating beforehand certain auxiliary functions of the coefficients of a polynomial \(P\), every subsequent evaluation of \(P\) can be performed with about half the number of multiplications that would be otherwise required. However, the auxiliary functions involved were obtained from the coefficients of \(P\) by solving high-degreed algebraic equations. Here we show that near optimal results can be obtained by use of rational auxiliary functions. We develop a variety of such rational preparation schemes for a variety of problems.
Reviewer: Michael O. Rabin
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0238.12002

Cited in 8 Documents

MSC:

11Y16 Number-theoretic algorithms; complexity
68W30 Symbolic computation and algebraic computation
11R09 Polynomials (irreducibility, etc.)
11C08 Polynomials in number theory

Keywords:

number of additions and multiplications; evaluation of monic polynomials; preconditioning; solution of high-order algebraic equations; asymptotic results; polynomials in several variables; rational functions; matrix polynomials
Cite Review PDF
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Length of shortest addition chain for n.

References:

[1] Belaga, Problemy Kibernet. 5 pp 7– (1961)
[2] The Art of Programming, Vol. 2, Addison-Wesley Pub. Co., 1969.
[3] Motzkin, Bulletin American Mathematical Society 61 pp 163– (1955)
[4] Pan, A.M.S. Russian Mathematical Surveys 21 pp 105– (1966)
[5] and , Bounds on the evaluation times for polynomials, Proc. of the 12 th IEEE Annual Symposium on Switching and Automata Theory, 1971, pp. 140–143.
[6] Winograd, Comm. Pure App. Math. 23 pp 165– (1970)
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.