We present a fast method for polynomial evaluation at points in arithmetic progression. By dividing the progression into m new ones and evaluating the polynomial at each point of these new progressions recursively,thi...We present a fast method for polynomial evaluation at points in arithmetic progression. By dividing the progression into m new ones and evaluating the polynomial at each point of these new progressions recursively,this method saves most of the multiplications in the price of little increase of additions comparing to Horner's method, while their accuracy are almost the same. We also introduce vector structure to the recursive process making it suitable for parallel applications.展开更多
Several algorithms based on homogeneous polynomials for multiplication of large integers are described in the paper. The homogeneity of polynomials provides several simplifications: reduction of system of equations an...Several algorithms based on homogeneous polynomials for multiplication of large integers are described in the paper. The homogeneity of polynomials provides several simplifications: reduction of system of equations and elimination of necessity to evaluate polynomials in points with larger coordinates. It is demonstrated that a two-stage implementation of the proposed and Toom-Cook algorithms asymptotically require twice as many standard multiplications than their direct implementation. A multistage implementation of these algorithms is also less efficient than their direct implementation. Although the proposed algorithms as well as the corresponding Toom-Cook algorithms require numerous algebraic additions, the Generalized Horner rule for evaluation of homogeneous polynomials, provided in the paper, decrease this number twice.展开更多
基金Supported by the Graduate Starting Seed Fund of Northwestern Polytechnical University(Z2012030)
文摘We present a fast method for polynomial evaluation at points in arithmetic progression. By dividing the progression into m new ones and evaluating the polynomial at each point of these new progressions recursively,this method saves most of the multiplications in the price of little increase of additions comparing to Horner's method, while their accuracy are almost the same. We also introduce vector structure to the recursive process making it suitable for parallel applications.
文摘Several algorithms based on homogeneous polynomials for multiplication of large integers are described in the paper. The homogeneity of polynomials provides several simplifications: reduction of system of equations and elimination of necessity to evaluate polynomials in points with larger coordinates. It is demonstrated that a two-stage implementation of the proposed and Toom-Cook algorithms asymptotically require twice as many standard multiplications than their direct implementation. A multistage implementation of these algorithms is also less efficient than their direct implementation. Although the proposed algorithms as well as the corresponding Toom-Cook algorithms require numerous algebraic additions, the Generalized Horner rule for evaluation of homogeneous polynomials, provided in the paper, decrease this number twice.
