登入選單

返回Google圖書搜尋

A Unified View of the Complexity of Evaluation and Interpolation

Cornell University. Department of Computer ScienceEllis Horowitz

出版	1973
URL	http://books.google.com.hk/books?id=DwgYcgAACAAJ&hl=&source=gbs_api

註釋

Four problems are considered: 1) from an n-precision integer compute its residues modulo n single precision primes; 2) from an n-degree polynomial compute its values at n points; 3) from n residues compute the unique n-precision integer congruent to the residues; 4) from n points compute the unique interpolating polynomial through those points. If $M(n)$ is the time for n-precision integer multiplication, then the time for problems 1 and 2 is shown to be $M(n) \log n$ and for problems 3 and 4 to be $M(n)(\log n)[superscript]{2}$. Moreover, it is shown that each of the four algorithms are really all instances of the same general algorithm. Finally, it is shown how preconditioning or a change of domain will reduce the time for problems 3 and 4 to $M(n)(\log n)$.