Simplification of radical expressions

ABSTRACT

In this paper we discuss the problem of simplifying unnested radical expressions. We describe an algorithm implemented in MACSYMA that simplifies radical expressions and then follow this description with a formal treatment of the problem. Theoretical computing times for some of the algorithms are briefly discussed as is related work of other authors.

REFERENCES

• 1: A. S. Besicovitch, On the Linear Independence of Fractional Powers of Integers, J. London Math. Soc. 15 (1940), 3-6.
• 2: W. S. Brown, On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors, Journal of the ACM (JACM), v.18 n.4, p.478-504, Oct. 1971 [doi>10.1145/321662.321664]
• 3: B. Buchberger, Ein Algorithmisches Kriterium für die Lösbarkeit eines Algebraischen Gleichungssystems, Aequationes Mathematicae 4 (1970).
• 4: B. F. Caviness, On Canonical Forms and Simplification, Ph.D. Dissertation, Carnegie-Mellon University (May, 1968), 80 pages. Available from Xerox University Microfilms, Ann Arbor, Michigan.
• 5: B. F. Caviness, On Canonical Forms and Simplification, Journal of the ACM (JACM), v.17 n.2, p.385-396, April 1970 [doi>10.1145/321574.321591]
• 6: George E. Collins, Quantifier elimination for real closed fields by cylindrical algebraic decomposition--preliminary report, ACM SIGSAM Bulletin, v.8 n.3, p.80-90, August 1974 [doi>10.1145/1086837.1086852]
• 7: Harvey Irwin Epstein, Algorithms for elementary transcendental function arithmetic., 1975
• 8: H. I. Epstein, Using basis computation to determine pseudo-multiplicative independence, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.229-237, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806340]
• 9: R. J. Fateman, ESSAYS IN ALGEBRAIC SIMPLIFICATION, Massachusetts Institute of Technology, Cambridge, MA, 1972
• 10: John P. Fitch, An Algebraic Manipulator, Ph.D. Dissertation, University of Cambridge (Oct. 1971).
• 11: John P. Fitch, On Algebraic Simplification, Computer J. 16 (1973), 23-27.
• 12: J. H. Griesmer, R. D. Jenks, and D. Y. Y. Yun, SCRATCHPAD Users Manual, Report RA 70, IBM Research Center, Yorktown Heights, N.Y. (June 1975), 66 pages.
• 13: S. L. Kleiman, Computing with Rational Expressions in Several Algebraically Dependent Variables, Bell Laboratories Tech. Report, Murray Hill, New Jersey, (1966), 40 pages. Reprinted as Computing Science Tech. Report #42 (1976).
• 14: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 15: Markus Lauer, Canonical representatives for residue classes of a polynomial ideal, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.339-345, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806353]
• 16: R. Loos, A Constructive Approach to Algebraic Numbers, preprint.
• 17: R. Loos, Toward a Formal Implementation of Computer Algebra, SIGSAM Bulletin 9, 3 (August 1975), 21-23.
• 18: W. A. Martin , R. J. Fateman, The MACSYMA system, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.59-75, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806267]
• 19: Mathlab Group, MACSYMA Reference Manual, The Laboratory for Computer Science, M.I.T., Cambridge, Massachusetts, (November 1975), 199 pages.
• 20: Joel Moses, Algebraic simplification: a guide for the perplexed, Communications of the ACM, v.14 n.8, p.527-537, Aug. 1971 [doi>10.1145/362637.362648]
• 21: Harry Pollard, The Theory of Algebraic Numbers, The Mathematical Association of America (1950).
• 22: Ian Richards, An Application of Galois Theory to Elementary Arithmetic, Adv. in Math. 13(1974), 268-273.
• 23: R. H. Risch, The Problem of Integration in Finite Terms, Trans. AMS, 139 (May 1969), 167-189.
• 24: R. H. Risch, Further Results on Elementary Functions, IBM Tech. Report RC 2402, Yorktown Heights, N.Y. (March 1969).
• 25: Cyrenus Matthew Rubald, Algorithms for polynomials over a real algebraic number field., 1973
• 26: Roman Shtokhamer, Simple Ideal Theory: Some Applications to Algebraic Simplification, University of Utah Tech. Report UCP-36 (July 1975), 22 pages.
• 27: Roman Shtokhamer, Simplification of Nested Radicals, University of Utah Tech. Report UCP-37 (July 1975), 16 pages.
• 28: B. L. van der Waerden, Modern Algebra, tr. F. Blum, Frederick Ungar Publ. Co. (1949).
• 29: Paul S. Wang, Factoring multivariate polynomials over algebraic number fields in MACSYMA, ACM SIGSAM Bulletin, v.9 n.3, p.21-23, August 1975 [doi>10.1145/1088309.1088316]
• 30: Peter Weinberger, Factoring Polynomials Over Algebraic Number Fields, ACM Trans. on Math. Software (to appear).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Simplification of expressions

General Terms:
Algorithms, Theory