学位(音乐)
数学
多项式的
整数(计算机科学)
组合数学
倒数多项式
插值(计算机图形学)
多项式插值
多项式次数
无平方多项式
时间复杂性
离散数学
稳定多项式
师(数学)
矩阵多项式
线性插值
计算机科学
算术
数学分析
动画
物理
计算机图形学(图像)
声学
程序设计语言
作者
Robert T. Moenck,Allan Borodin
摘要
It is shown that the problem of evaluating an Nth degree polynomial is reducible to the problem of dividing the polynomial. A method for dividing an Nth degree polynomial by an N/2 degree polynomial in O(N log 2N) steps is given. Using this it is shown that the evaluation of an Nth degree polynomial at N points can be done in O(N log 3N). The related problem of computing of computing the resides of an N precision integer is handed by the same algorithm in O(N log2N loglogN) steps. Using the methods of Horowitz11 and Heindel8 it is shown that interpolation of an Nth degree polynomial is redicible to the problem of evaluating an Nth degree polynomial at N points. An algorithm for preconditioned polynomial interpolation requiring O(N log 2N) steps is presented. This is then extended to perform the complete interpolation in O(N log 3N) steps. A modified version of Reminider Problem in O(N log 2N loglogN) steps.
科研通智能强力驱动
Strongly Powered by AbleSci AI