% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\FactoredXmpTitle}{Factored}
\newcommand{\FactoredXmpNumber}{9.22}
%
% =====================================================================
\begin{page}{FactoredXmpPage}{9.22 Factored}
% =====================================================================
\beginscroll

\spadtype{Factored} creates a domain whose objects are kept in factored
%-% \HDindex{factorization}{FactoredXmpPage}{9.22}{Factored}
form as long as possible.
Thus certain operations like \spadopFrom{*}{Factored}
(multiplication) and \spadfunFrom{gcd}{Factored} are relatively
easy to do.
Others, such as addition, require somewhat more work, and
the result may not be completely factored
unless the argument domain \spad{R} provides a
\spadfunFrom{factor}{Factored} operation.
Each object consists of a unit and a list of factors, where each
factor consists of a member of \spad{R} (the {\em base}), an
exponent, and a flag indicating what is known about the base.
A flag may be one of \spad{"nil"}, \spad{"sqfr"}, \spad{"irred"}
or \spad{"prime"}, which mean that nothing is known about the
base, it is square-free, it is irreducible, or it is prime,
respectively.
The current restriction to factored objects of integral domains
allows simplification to be performed without worrying about
multiplication order.

\beginmenu
    \menudownlink{{9.22.1. Decomposing Factored Objects}}{ugxFactoredDecompPage}
    \menudownlink{{9.22.2. Expanding Factored Objects}}{ugxFactoredExpandPage}
    \menudownlink{{9.22.3. Arithmetic with Factored Objects}}{ugxFactoredArithPage}
    \menudownlink{{9.22.4. Creating New Factored Objects}}{ugxFactoredNewPage}
    \menudownlink{{9.22.5. Factored Objects with Variables}}{ugxFactoredVarPage}
\endmenu
\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugxFactoredDecompTitle}{Decomposing Factored Objects}
\newcommand{\ugxFactoredDecompNumber}{9.22.1.}
%
% =====================================================================
\begin{page}{ugxFactoredDecompPage}{9.22.1. Decomposing Factored Objects}
% =====================================================================
\beginscroll

\labelSpace{4pc}
\xtc{
In this section we will work with a factored integer.
}{
\spadpaste{g := factor(4312) \bound{g}}
}
\xtc{
Let's begin by decomposing \spad{g} into pieces.
The only possible units for integers are \spad{1} and \spad{-1}.
}{
\spadpaste{unit(g) \free{g}}
}
\xtc{
There are three factors.
}{
\spadpaste{numberOfFactors(g) \free{g}}
}
\xtc{
We can make a list of the bases, \ldots
}{
\spadpaste{[nthFactor(g,i) for i in 1..numberOfFactors(g)] \free{g}}
}
\xtc{
and the exponents, \ldots
}{
\spadpaste{[nthExponent(g,i) for i in 1..numberOfFactors(g)] \free{g}}
}
\xtc{
and the flags.
You can see that all the bases (factors) are prime.
}{
\spadpaste{[nthFlag(g,i) for i in 1..numberOfFactors(g)] \free{g}}
}
\xtc{
A useful operation for pulling apart a factored object into a list
of records of the components is \spadfunFrom{factorList}{Factored}.
}{
\spadpaste{factorList(g) \free{g}}
}
\xtc{
If you don't care about the flags, use \spadfunFrom{factors}{Factored}.
}{
\spadpaste{factors(g) \free{g}\bound{prev1}}
}
\xtc{
Neither of these operations returns the unit.
}{
\spadpaste{first(\%).factor \free{prev1}}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugxFactoredExpandTitle}{Expanding Factored Objects}
\newcommand{\ugxFactoredExpandNumber}{9.22.2.}
%
% =====================================================================
\begin{page}{ugxFactoredExpandPage}{9.22.2. Expanding Factored Objects}
% =====================================================================
\beginscroll

\labelSpace{4pc}
\xtc{
Recall that we are working with this factored integer.
}{
\spadpaste{g := factor(4312) \bound{g}}
}
\xtc{
To multiply out the factors with their multiplicities, use
\spadfunFrom{expand}{Factored}.
}{
\spadpaste{expand(g) \free{g}}
}
\xtc{
If you would like, say, the distinct factors multiplied together
but with multiplicity one, you could do it this way.
}{
\spadpaste{reduce(*,[t.factor for t in factors(g)]) \free{g}}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugxFactoredArithTitle}{Arithmetic with Factored Objects}
\newcommand{\ugxFactoredArithNumber}{9.22.3.}
%
% =====================================================================
\begin{page}{ugxFactoredArithPage}{9.22.3. Arithmetic with Factored Objects}
% =====================================================================
\beginscroll

\labelSpace{4pc}
\xtc{
We're still working with this factored integer.
}{
\spadpaste{g := factor(4312) \bound{g}}
}
\xtc{
We'll also define this factored integer.
}{
\spadpaste{f := factor(246960) \bound{f}}
}
\xtc{
Operations involving multiplication and division are particularly
easy with factored objects.
}{
\spadpaste{f * g \free{f g}}
}
\xtc{
}{
\spadpaste{f**500 \free{f}}
}
\xtc{
}{
\spadpaste{gcd(f,g) \free{f g}}
}
\xtc{
}{
\spadpaste{lcm(f,g) \free{f g}}
}
\xtc{
If we use addition and subtraction things can slow down because
we may need to compute greatest common divisors.
}{
\spadpaste{f + g \free{f g}}
}
\xtc{
}{
\spadpaste{f - g \free{f g}}
}
\xtc{
Test for equality with \spad{0} and \spad{1} by using
\spadfunFrom{zero?}{Factored} and \spadfunFrom{one?}{Factored},
respectively.
}{
\spadpaste{zero?(factor(0))}
}
\xtc{
}{
\spadpaste{zero?(g) \free{g}}
}
\xtc{
}{
\spadpaste{one?(factor(1))}
}
\xtc{
}{
\spadpaste{one?(f) \free{f}}
}
\xtc{
Another way to get the zero and one factored objects is to use
package calling (see \downlink{``\ugTypesPkgCallTitle''}{ugTypesPkgCallPage} in Section \ugTypesPkgCallNumber\ignore{ugTypesPkgCall}).
}{
\spadpaste{0\$Factored(Integer)}
}
\xtc{
}{
\spadpaste{1\$Factored(Integer)}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugxFactoredNewTitle}{Creating New Factored Objects}
\newcommand{\ugxFactoredNewNumber}{9.22.4.}
%
% =====================================================================
\begin{page}{ugxFactoredNewPage}{9.22.4. Creating New Factored Objects}
% =====================================================================
\beginscroll

The \spadfunFrom{map}{Factored} operation is used to iterate across the
unit and bases of a factored object.
See \downlink{`FactoredFunctions2'}{FactoredFunctionsTwoXmpPage}\ignore{FactoredFunctions2} for a discussion of
\spadfunFrom{map}{Factored}.

\labelSpace{1pc}
\xtc{
The following four operations take a base and an exponent and create
a factored object.
They differ in handling the flag component.
}{
\spadpaste{nilFactor(24,2) \bound{prev2}}
}
\xtc{
This factor has no associated information.
}{
\spadpaste{nthFlag(\%,1) \free{prev2}}
}
\xtc{
This factor is asserted to be square-free.
}{
\spadpaste{sqfrFactor(30,2) \bound{prev3}}
}
\xtc{
This factor is asserted to be irreducible.
}{
\spadpaste{irreducibleFactor(13,10) \bound{prev4}}
}
\xtc{
This factor is asserted to be prime.
}{
\spadpaste{primeFactor(11,5) \bound{prev5}}
}

\xtc{
A partial inverse to \spadfunFrom{factorList}{Factored} is
\spadfunFrom{makeFR}{Factored}.
}{
\spadpaste{h := factor(-720) \bound{h}}
}
\xtc{
The first argument is the unit and the second is a list of records as
returned by \spadfunFrom{factorList}{Factored}.
}{
\spadpaste{h - makeFR(unit(h),factorList(h)) \free{h}}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugxFactoredVarTitle}{Factored Objects with Variables}
\newcommand{\ugxFactoredVarNumber}{9.22.5.}
%
% =====================================================================
\begin{page}{ugxFactoredVarPage}{9.22.5. Factored Objects with Variables}
% =====================================================================
\beginscroll

\labelSpace{4pc}
\xtc{
Some of the operations available for polynomials are also available
for factored polynomials.
}{
\spadpaste{p := (4*x*x-12*x+9)*y*y + (4*x*x-12*x+9)*y + 28*x*x - 84*x + 63 \bound{p}}
}
\xtc{
}{
\spadpaste{fp := factor(p) \free{p}\bound{fp}}
}
\xtc{
You can differentiate with respect to a variable.
}{
\spadpaste{D(p,x) \free{p}}
}
\xtc{
}{
\spadpaste{D(fp,x) \free{fp}\bound{prev1}}
}
\xtc{
}{
\spadpaste{numberOfFactors(\%) \free{prev1}}
}
\endscroll
\autobuttons
\end{page}
%