Recent technical reports
Recent technical reports
复制标题
DOI：
10.1145/1008348.1008352
复制
发表时间：
1977
期刊：
影响因子：
--
通讯作者：
M. Shamos
中科院分区：
文献类型：
--
作者：
M. Shamos
Certain questions concerning the arithmetic complexity of unlvarlate polynomial evaluation are considered. Given an operator which maps polynomials to sets of polynomials, the objective is to investigate the relative savings in arithmetic operations achievable by evaluating some polynomlai h(x) ~ g(f(x)) rather than f(x). The main technical results concern the operator that maps f to the set of nontrlvlal polynomial multiples of f. It is shown that there exist polynomials f, g, and h, with h fg, such that h requires substantlally fewer arithmetic operations than either f or g. However, if the coefficients of f are algebraically independent, then any h fg Is as hard to evaluate as f. Several observations and open questions concerning other operators are discussed.
