Chinese remainder and interpolation algorithms

ABSTRACT

This paper is concerned with mathematical, computational, and historical aspects of the Chinese Remainder and Interpolation Theorems of number theory and numerical analysis, with a view to their application to symbolic computation.

REFERENCES

• 1: Albert, A. A., Fundamental Concepts of Algebra, University of Toronto Press, Toronto, 1956.
• 2: Bell, E. T., The Development of Mathematics, McGraw-Hill Book Co., New York, 1945.
• 3: Borosh, I. and A. S. Fraenkel, "Exact Solution of Linear Equations with Rational Coefficients by Congruence Techniques", Mathematics of Computation, Vol. 20, No. 93 (Jan. 1966), pp. 107-112.
• 4: Stanley Cabay, Exact solution of linear equations, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.392-398, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806310]
• 5: Collins, G. E. et al., The SAC-1 Modular Arithmetic System, University of Wisconsin Computing Center, Technical Reference No. 10, June 1969.
• 6: Dickson, L. E., History of the Theory of Numbers, Chelsea Publishing Co., New York, 1952.
• 7: Fadeeva, V. N., Computational Methods of Linear Algebra, Dover Publications, Inc., New York, 1959.
• 8: Gauss, C. F., Disquisitiones Arithmeticae, Translated by A. A. Clarke, Yale University Press, New Haven, 1966.
• 9: Gauss, C. F., Werke III, Nachlass. Theoria Interpolations Methods Nova Tractata.
• 10: Greenstreet, W. J. (Editor), Isaac Newton 1642-1727, G. Bell and Sons, Ltd., London, 1927.
• 11: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 12: Lagrange, J.-L., Oeuvres, Vol. 7 (Les Lecons Elementaires sur les Mathematiques - Lecon Cinquieme: Sur 1'usage des Courbes dans la solution des Problèmes, p. 286 (1795)).
• 13: Mac Lane, S. and G. Birkhoff, Algebra, The Macmillan Company, New York, 1967.
• 14: Newman, M., "Solving Equations Exactly", J. Res. Nat. Bur. Standards, Vol. 71B, No. 4 (Oct.-Dec. 1967), pp. 171-179.
• 15: Newton, I., Mathematical Principles of Natural Philosophy and his System of the World, Revised Translation by F. Cajori, University of California Press, Berkeley, California, 1960.
• 16: Ore, O., Number Theory and its History, McGraw-Hill Book Co., New York, 1948.
• 17: Szabo, N. S., and R. I. Tanaka, Residue Arithmetic and its Applications to Computer Technology, McGraw-Hill Book Company, New York, 1967.
• 18: Takahasi, H. and Y. Ishibashi, "A New Method for Exact Calculation by a Digital Computer", Information Processing in Japan, Vol. 1 (1961), pp. 28-42.
• 19: Waring, E., "Problems Concerning Interpolations", Phil. Trans. of the Royal Soc. of London, Vol. 59, (1779), pp. 59-67.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.0 General

  K. Computing Milieux
  K.2 HISTORY OF COMPUTING
      Subjects: Theory

General Terms:
Algorithms, Theory