Polynomials
===========

A "polynomial" is a sum of terms which are coefficients times various
powers of a "base" variable.  For example, `2 x^2 + 3 x - 4' is a
polynomial in `x'.  Some formulas can be considered polynomials in
several different variables: `1 + 2 x + 3 y + 4 x y^2' is a polynomial
in both `x' and `y'.  Polynomial coefficients are often numbers, but
they may in general be any formulas not involving the base variable.

The `a f' (`calc-factor') [`factor'] command factors a polynomial into
a product of terms.  For example, the polynomial `x^3 + 2 x^2 + x' is
factored into `x*(x+1)^2'.  As another example, `a c + b d + b c + a
d' is factored into the product `(a + b) (c + d)'.

Calc currently has three algorithms for factoring.  Formulas which are
linear in several variables, such as the second example above, are
merged according to the distributive law.  Formulas which are
polynomials in a single variable, with constant integer or fractional
coefficients, are factored into irreducible linear and/or quadratic
terms.  The first example above factors into three linear terms (`x',
`x+1', and `x+1' again).  Finally, formulas which do not fit the above
criteria are handled by the algebraic rewrite mechanism.

Calc's polynomial factorization algorithm works by using the general
root-finding command (`a P') to solve for the roots of the
polynomial.  It then looks for roots which are rational numbers
or complex-conjugate pairs, and converts these into linear and
quadratic terms, respectively.  Because it uses floating-point
arithmetic, it may be unable to find terms that involve large
integers (whose number of digits approaches the current precision).
Also, irreducible factors of degree higher than quadratic are not
found, and polynomials in more than one variable are not treated.
(A more robust factorization algorithm may be included in a future
version of Calc.)

The rewrite-based factorization method uses rules stored in the
variable `FactorRules'.  See Rewrite Rules, for a discussion of
the operation of rewrite rules.  The default `FactorRules' are able to
factor quadratic forms symbolically into two linear terms, `(a x + b)
(c x + d)'.  You can edit these rules to include other cases if you
wish.  To use the rules, Calc builds the formula `thecoefs(x, [a, b,
c, ...])' where `x' is the polynomial base variable and `a', `b',
etc., are polynomial coefficients (which may be numbers or formulas).
The constant term is written first, i.e., in the `a' position.  When
the rules complete, they should have changed the formula into the form
`thefactors(x, [f1, f2, f3, ...])'  where each `fi' should be a
factored term, e.g., `x - ai'.  Calc then multiplies these terms
together to get the complete factored form of the polynomial.  If the
rules do not change the `thecoefs' call to a `thefactors' call, `a f'
leaves the polynomial alone on the assumption that it is unfactorable.
(Note that the function names `thecoefs' and `thefactors' are used
only as placeholders; there are no actual Calc functions by those
names.)

The `H a f' [`factors'] command also factors a polynomial, but it
returns a list of factors instead of an expression which is the
product of the factors.  Each factor is represented by a sub-vector of
the factor, and the power with which it appears.  For example, `x^5 +
x^4 - 33 x^3 + 63 x^2' factors to `(x + 7) x^2 (x - 3)^2' in `a f', or
to `[ [x, 2], [x+7, 1], [x-3, 2] ]' in `H a f'.  If there is an
overall numeric factor, it always comes first in the list.  The
functions `factor' and `factors' allow a second argument when written
in algebraic form; `factor(x,v)' factors `x' with respect to the
specific variable `v'.  The default is to factor with respect to all
the variables that appear in `x'.

The `a c' (`calc-collect') [`collect'] command rearranges a formula as
a polynomial in a given variable, ordered in decreasing powers of that
variable.  For example, given `1 + 2 x + 3 y + 4 x y^2' on the stack,
`a c x' would produce `(2 + 4 y^2) x + (1 + 3 y)', and `a c y' would
produce `(4 x) y^2 + 3 y + (1 + 2 x)'.  The polynomial will be
expanded out using the distributive law as necessary: Collecting `x'
in `(x - 1)^3' produces `x^3 - 3 x^2 + 3 x - 1'.  Terms not involving
`x' will not be expanded.

The "variable" you specify at the prompt can actually be any
expression: `a c ln(x+1)' will collect together all terms multiplied
by `ln(x+1)' or integer powers thereof.  If `x' also appears in the
formula in a context other than `ln(x+1)', `a c' will treat those
occurrences as unrelated to `ln(x+1)', i.e., as constants.

The `a x' (`calc-expand') [`expand'] command expands an expression by
applying the distributive law everywhere.  It applies to products,
quotients, and powers involving sums.  By default, it fully
distributes all parts of the expression.  With a numeric prefix
argument, the distributive law is applied only the specified number of
times, then the partially expanded expression is left on the stack.

The `a x' and `j D' commands are somewhat redundant.  Use `a x' if you
want to expand all products of sums in your formula.  Use `j D' if you
want to expand a particular specified term of the formula.  There is
an exactly analogous correspondence between `a f' and `j M'.  (The `j
D' and `j M' commands also know many other kinds of expansions, such
as `exp(a + b) = exp(a) exp(b)', which `a x' and `a f' do not do.)

Calc's automatic simplifications will sometimes reverse a partial
expansion.  For example, the first step in expanding `(x+1)^3' is to
write `(x+1) (x+1)^2'.  If `a x' stops there and tries to put this
formula onto the stack, though, Calc will automatically simplify it
back to `(x+1)^3' form.  The solution is to turn simplification off
first (See Simplification Modes), or to run `a x' without a
numeric prefix argument so that it expands all the way in one step.

The `a a' (`calc-apart') [`apart'] command expands a rational function
by partial fractions.  A rational function is the quotient of two
polynomials; `apart' pulls this apart into a sum of rational functions
with simple denominators.  In algebraic notation, the `apart' function
allows a second argument that specifies which variable to use as the
"base"; by default, Calc chooses the base variable automatically.

The `a n' (`calc-normalize-rat') [`nrat'] command attempts to arrange
a formula into a quotient of two polynomials.  For example, given `1 +
(a + b/c) / d', the result would be `(b + a c + c d) / c d'.  The
quotient is reduced, so that `a n' will simplify `(x^2 + 2x + 1) /
(x^2 - 1)' by dividing out the common factor `x + 1', yielding `(x +
1) / (x - 1)'.

The `a \' (`calc-poly-div') [`pdiv'] command divides two polynomials
`u' and `v', yielding a new polynomial `q'.  If several variables
occur in the inputs, the inputs are considered multivariate
polynomials.  (Calc divides by the variable with the largest power in
`u' first, or, in the case of equal powers, chooses the variables in
alphabetical order.)  For example, dividing `x^2 + 3 x + 2' by `x + 2'
yields `x + 1'.  The remainder from the division, if any, is reported
at the bottom of the screen and is also placed in the Trail along with
the quotient.

Using `pdiv' in algebraic notation, you can specify the particular
variable to be used as the base: `pdiv(a,b,x)'.  If `pdiv' is given
only two arguments (as is always the case with the `a \' command),
then it does a multivariate division as outlined above.

The `a %' (`calc-poly-rem') [`prem'] command divides two polynomials
and keeps the remainder `r'.  The quotient `q' is discarded.  For any
formulas `a' and `b', the results of `a \' and `a %' satisfy `a = q b
+ r'.  (This is analogous to plain `\' and `%', which compute the
integer quotient and remainder from dividing two numbers.)

The `a /' (`calc-poly-div-rem') [`pdivrem'] command divides two
polynomials and reports both the quotient and the remainder as a
vector `[q, r]'.  The `H a /' [`pdivide'] command divides two
polynomials and constructs the formula `q + r/b' on the stack.
(Naturally if the remainder is zero, this will immediately simplify to
`q'.)

The `a g' (`calc-poly-gcd') [`pgcd'] command computes the greatest
common divisor of two polynomials.  (The GCD actually is unique only
to within a constant multiplier; Calc attempts to choose a GCD which
will be unsurprising.)  For example, the `a n' command uses `a g' to
take the GCD of the numerator and denominator of a quotient, then
divides each by the result using `a \'.  (The definition of GCD
ensures that this division can take place without leaving a
remainder.)

While the polynomials used in operations like `a /' and `a g' often
have integer coefficients, this is not required.  Calc can also deal
with polynomials over the rationals or floating-point reals.
Polynomials with modulo-form coefficients are also useful in many
applications; if you enter `(x^2 + 3 x - 1) mod 5', Calc automatically
transforms this into a polynomial over the field of integers mod 5:
`(1 mod 5) x^2 + (3 mod 5) x + (4 mod 5)'.

Congratulations and thanks go to Ove Ewerlid
(`ewerlid@mizar.DoCS.UU.SE'), who contributed many of the polynomial
routines used in the above commands.

See Decomposing Polynomials, for several useful functions for
extracting the individual coefficients of a polynomial.