9.3 Cancellation of Common Factors

Facilities are available in REDUCE for cancelling common factors in the numerators and denominators of expressions, at the option of the user. The system will perform this greatest common divisor computation if the switch gcd is on. (gcd is normally off.)

A check is automatically made, however, for common variable and numerical products in the numerators and denominators of expressions, and the appropriate cancellations made.

When gcd is on, and exp is off, a check is made for square free factors in an expression. This includes separating out and independently checking the content of a given polynomial where appropriate. (For an explanation of these terms, see [Hea79].)

Example: With exp off and gcd on, the polynomial a*c+a*d+b*c+b*d would be returned as (a+b)*(c+d).

Under normal circumstances, GCDs are computed using an algorithm described in the above paper. It is also possible in REDUCE to compute GCDs using an alternative algorithm, called the EZGCD Algorithm, which uses modular arithmetic. The switch ezgcd, if on in addition to gcd, makes this happen.

In non-trivial cases, the EZGCD algorithm is almost always better than the basic algorithm, often by orders of magnitude. We therefore strongly advise users to use the ezgcd switch where they have the resources available for supporting the package.

For a description of the EZGCD algorithm, [MY73].

NOTE: This package shares code with the factorizer, so a certain amount of trace information can be produced using the factorizer trace switches.

An implementation of the heuristic GCD algorithm, first introduced by B.W. Char, K.O. Geddes and G.H. Gonnet, as described in [DP85], is also available on an experimental basis. To use this algorithm, the switch heugcd should be on in addition to gcd. Note that if both ezgcd and heugcd are on, the former takes precedence.

9.3.1 Determining the GCD of Two Polynomials

This operator, used with the syntax

    gcd(exprn1:polynomial,exprn2:polynomial):polynomial,

returns the greatest common divisor of the two polynomials exprn1 and exprn2.

Examples:

        gcd(x^2+2*x+1,x^2+3*x+2) ->  x+1
        gcd(2*x^2-2*y^2,4*x+4*y) ->  2*x+2*y
        gcd(x^2+y^2,x-y)         ->  1.

Hosted by