A unified view of the complexity of evaluation and interpolation

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) 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).