Factored -- the domain of
objects kept in factored form
IntroductionFactored is the domain of objects kept in factored
form, such as prime factorization of integers, square-free
factorization of polynomials, or the factorization of polynomials in
irreducible factors.
Creating
ElementsFactored(list <, type> <, ring>)
Factored(f <, type> <, ring>)
Parameterslist |
- | a list of odd length |
f |
- | an arithmetical expression |
type |
- | a string (default:
"unknown") |
ring |
- | a domain of category Cat::IntegralDomain (default:
Dom::ExpressionField()) |
Detailslist must be a list of odd length and of
the form [u, f1, e1, f2, e2, ..., fr, er], where the
entries u and fi are elements of the domain
ring, or can be converted into such elements. The
ei must be integers. Here, i ranges from
1 to r.
See section ``Operands'' below for the meaning of the entries of that list.
An error message is reported, if one of the list entries is of wrong type.
f given as the first
argument is the same as giving the list [ring::one, f, 1].
See section ``Operands'' below for the meaning of the entries of that list.
f must be an element of the domain ring,
or must be convertible into such an element, otherwise an error message
would be given.
type indicates what is known about the
factorization. Currently, the following types are known:
"unknown" - nothing is known about the
factorization."irreducible" - the fi are irreducible over
the domain ring."squarefree" - the fi are square-free over
the domain ring.If this argument is missing, then the type of the created factored
object is set to "unknown".
The type of factorization is known to any element of
Factored. Use the methods "getType" and
"setType" (see below) to read and set the type of
factorization of a given factored object.
ring is the ring of factorization. It
must be an integral domain, i.e., a domain of category Cat::IntegralDomain.
If this argument is missing, then the domain Dom::ExpressionField() is
used.
The ring of factorization is known to any element of
Factored. Use the methods "getRing" and
"setRing" (see below) to read and set the ring of
factorization of a given factored object.
[ ] to extract the operands of an
element f of the domain Factored, i.e.,
f[1] = u, f[2] = f1, f[3] = e1, ....
For example, to extract all factors fi, enter
f[2*i] $ i = 1..nops(f) div 2. To extract all exponents
ei, enter f[2*i + 1] $ i = 1..nops(f) div
2.
You can also use the methods "factors" and
"exponents" (see below) to access the operands, i.e., the
call Factored::factors(f) returns a list of the factors
fi, and Factored::exponents(g) returns a list
of the exponents ei (1<=i<=r).
ifactor, factor and polylib::sqrfree are the main
application of this domain, they return their result in form of such
factored objects (see their help pages for information about the type
and ring of factorization).
There may be no need to explicitly create factored objects, but to work with the results of the mentioned system functions.
Factored is printed like an
expression and behaves like that. As an example, the result of f
:= factor(x^2 + 2*x + 1) is an element of Factored
and printed as (x + 1)^2. The call type(f) returns "_power"
as the expression type of f.f of Factored, the call
Factored::convert(f, DOM_LIST) gives a list of all
operands of f.An element f of Factored consists of the
r+1 operands u, f1, e1, f2, e2,..., fr, er, such
that f = u * f1^e1 * f2^e2 * ... * fr^er.
The first operand u and the factors fi are
elements of the domain ring. The exponents ei
are integers.
You can apply (almost) each function to factored objects, functions that mainly expect arithmetical expressions as their input.
For example, one may add or multiply those objects, or apply
functions such as expand and diff to them. But the result of such an
operation then is usually not any longer of the domain
Factored, as the factored form could be lost due to the
operation (see examples below).
Call expr(f) to
convert the factored object f into an arithmetical
expression (as an element of a kernel domain).
The call coerce(f,
DOM_LIST) returns a list of operands of the factored object
f (see method "convert_to" below).
Evaluating an object of type Factored returns
itself.
Calling a factored object as a function yields the object itself, regardless of the arguments. The arguments are not evaluated.
_mult(Factored f, any
g...)g is an element of the domain
ring (or can be converted into such an element).
If g is a unit of ring or a factor of
f, then the result is a factored object of the same
factorization type as f. Otherwise, the result is an
element of Factored with the factorization type
"unknown".
f and g are factored objects with
factorization type "irreducible", then the result is again
a factored object of this type, i.e., the result is still in factored
form.f is lost, and the
result of this method is an element of ring._mult for factored objects, i.e., one
may use it in the form f*g*..., or in functional notation:
_mult(f, g...)._power(Factored f, any n)n is a positive integer and f a
factored object with factorization type "irreducible" or
"squarefree", then the result is still a factored object
of this type.f is lost, and the
result of this method is an element of ring._power for factored objects, i.e.,
one may use it in the form f^n, or in functional notation:
_power(f, n).expand(Factored f)f in expanded form. The result of this method
is an element of ring.exponents(Factored f)f.factor(Factored f)f into irreducible factors.f already is of the factorization type
"irreducible", then this method just return
f.
Otherwise, this method converts f into an element of
the domain ring and calls the method "factor"
of ring.
This method returns a factored object of the domain
Factored with factorization type
"irreducible", if the factorization of f can
be computed (otherwise, FAIL is returned).
factor for factored objects, i.e.,
one may use it in the form factor(f).factors(Factored f)f.irreducible(Factored f)TRUE, if f is irreducible over
the integral domain ring, otherwise
FALSE.f has the
factorization type "irreducible".
Otherwise, this method converts f into an element of
ring and calls the method "irreducible" of
ring. The value FAIL is returned, if the
domain ring cannot test if f is
irreducible.
iszero(Factored f)TRUE if f is zero, and
FALSE otherwise.iszero for factored objects, i.e.,
one may use it in the form iszero(f).sqrfree(Factored f)f into square-free factors.f already is of the factorization type
"squarefree", then this method just return f.
Otherwise, this method converts f into an element of
the domain ring and calls the method
"squarefree" of ring.
This method returns a factored object of the domain
Factored with factorization type
"squarefree", if the square-free factorization of
f can be computed (otherwise, FAIL is
returned).
polylib::sqrfree for factored
objects, i.e., one may use it in the form
polylib::sqrfree(f)._index(Factored f, positive integer i)i-th operand of f (see above
for a description of the operands of such elements).i is greater than
the number of operands of f.[ ] for factored objects, i.e., one
may use it in the form f[i].getRing(Factored f)ring of f.getType(Factored f)type of
f.map(Factored f, function func...)f into the unevaluated
expression u*f1^e1*f2^e2*...*fr^er, where u, f1, e1,
... are the operands of f. Then the function
func is mapped to that expression.
Note that the result of this method is not longer an object of
Factored!
map for details.map for factored objects, i.e., one may
use it in the form map(f, function
func...).nops(Factored f)f (see above for a
description of the operands of such elements).nops for factored objects, i.e., one
may use it in the form nops(f).op(Factored f, positive
integer i)i-th operand of f (see above
for a description of the operands of such elements).FAIL, if i is greater than the
number of operands of f.op for factored objects, i.e., one may
use it in the form op(f, i).set_index(Factored f, positive integer i, any x)i-th operand of f to the value
of x (see above for a description of the operands of such
elements).
The factorization type of f is set to
"unknown".
i is greater than
the number of operands of f.
Make sure that x either is an element
of the domain ring, or an integer.
[ ] for factored objects, i.e., one
may use it in the form f[i].setRing(Factored f, domain ring)f to the domain
ring.Use this method with caution! Make sure that the
factorization of f is still valid over the new ring, and
that the operands of f have the correct domain type.
ring must be a domain of category Cat::IntegralDomain, which is
not checked by this method.
setType(Factored f, string type)f to
type.Use this method with caution! Make sure that the
factorization type corresponds with the factorization of
f.
type(Factored f)f into the unevaluated expression
u*f1^e1*f2^e2*...*fr^er and returns its expression type
that is either "_power", "_mult", or the type
of an element of the domain ring.convert(any x)x into an element of the
domain type Factored.FAIL is returned.x may either be a list of the form [u, f1, e1,
..., fr, er] of odd length (where u, f1, ..., fr
are of the domain type ring, or can be converted into such
elements, and e1, ..., er are integers), or an element
that can be converted into the domain ring. The latter
case corresponds to the list [ring::one,x,1].convert_to(Factored f, any T)f
into an element of domain type T, or, if T is
not a domain, to the domain type of T.FAIL is returned.T is the domain DOM_LIST, then the list of operands
of f is returned.
If T is the domain DOM_EXPR, then the unevaluated
expression u*f1^e1*f2^e2*...*fr^er is returned, where
u, f1, e1, ... are the operands of f.
Otherwise, the method "convert" of the domain
T is called to convert f into an element of
the domain T (which could return FAIL).
expr
to convert f into an object of a kernel domain (see
below).create(list list)list have the correct form and type of
elements (see the description of the operands of a factored
object).create(ring x)ring::one, x, 1.expr(Factored f)f into an object of a kernel
domain, applying the method "expr" of the domain
ring to each factor of f.Note that the factored form of f may be
lost due to this conversion.
expr2text(Factored f)f to a string.testtype(Factored f, domain T)f can be converted into an element of the
domain T, and returns TRUE or
FAIL, respectively.
This method uses the method "convert" (see above) into
check, if a conversion is possible.
testtype.TeX(Factored f)f."TeX" of the domain ring is
used to get the LaTeX-representation of the corresponding operands of
f.generate::TeX._concat(Factored f, Factored g)g to the operands of f. The
first operand of the new factored object is the first operand of
f multiplied by the first operand of g.
The factorization type of the new factored object is set to
"unknown".
f and g must have the same factorization
type and factorization ring, otherwise an error message is given.maprec(Factored f, any x...)misc::maprec and allows recursive
mapping for factored objects. See the corresponding help page of this
function for details.f is converted into the unevaluated expression
u*f1^e1*f2^e2*...*fr^er, where u, f1, e1, ...
are the operands of f. Then the function
misc::maprec is called with this expression as its first
parameter.
Note that the result of this method is not longer an object of
Factored!
print(Factored f)f. This method is
used from the system function print for printing factored objects to
the screen.unapply(Factored f <, identifier x>)f into an expression
e using the method "expr" (see above) and
interprets this expression as a function in x.... It
returns a procedure computing the expression e.fp::unapply for
factored objects, i.e., one may use it in the form
fp::unapply(f). See fp::unapply for details.
Example
1The following computes the prime factorization of the integer 20:
>> f := ifactor(20)
2
2 5
The result is an element of the domain
Factored:
>> domtype(f)
Factored
which consists of the following five operands:
>> op(f)
1, 2, 2, 5, 1
They represent the integer 20 in the following form: 20 = 1 * 2^2 * 5^1. The factors are prime numbers and can be extracted in two different ways:
>> Factored::factors(f), f[2*i] $ i = 1..nops(f) div 2
[2, 5], 2, 5
ifactor
kept the information, that the factorization ring is the ring of
integers (represented by the domain Dom::Integer), and that the factors of
f are prime (and therefore irreducible, because
Z is an integral domain):
>> Factored::getRing(f), Factored::getType(f)
Dom::Integer, "irreducible"
We can convert such an object into different forms, such as into a list of its operands:
>> Factored::convert_to(f, DOM_LIST)
[1, 2, 2, 5, 1]
or into an unevaluated expression, keeping the factored form:
>> Factored::convert_to(f, DOM_EXPR)
2
2 5
or back into an integer:
>> Factored::convert_to(f, Dom::Integer)
20
You may also use the system function convert here, which has the same
effect.
Example
2We compute the factorization of the integers 108 and 512:
>> n1 := ifactor(108); n2 := ifactor(512)
2 3
2 3
9
2
The multiplication of these two integers gives the prime factorization of 55296 = 108 * 512:
>> n1*n2
11 3
2 3
Note that the most operations on such objects lead to an un-factored form, such as adding these two integers:
>> n1 + n2
620
You may apply the function ifactor to the result, if you are
interested in its prime factorization:
>> ifactor(%)
2
2 5 31
You an apply (almost) each function to factored objects, functions that mainly expect arithmetical expressions as their input. Note that, before the operation is applied, the factored object is converted into an arithmetical expression in un-factored form:
>> Re(n1)
108
Example
3The second system function which deals with elements of
Factored, is factor, which computes all
irreducible factors of a polynomial.
For example, if we define the following polynomial of Zmod(101):
>> p := poly(x^12 + x + 1, [x], Dom::IntegerMod(101)):
and compute its factorization into irreducible factors, we get:
>> f := factor(p)
2
poly(x + 73 x + 29, [x], Dom::IntegerMod(101)) poly(
5 4 3 2
x + 62 x + 64 x + 63 x + 58 x + 100, [x],
5 4 3 2
Dom::IntegerMod(101)) poly(x + 67 x + 72 x + 100 x +
33 x + 94, [x], Dom::IntegerMod(101))
If we multiply the factored object with an element that
can be converted into an element of the ring of factorization, then we
get a new factored object, which then is of the factorization type
"unknown":
>> x*f
2
poly(x + 73 x + 29, [x], Dom::IntegerMod(101)) poly(
5 4 3 2
x + 62 x + 64 x + 63 x + 58 x + 100, [x],
5 4 3 2
Dom::IntegerMod(101)) poly(x + 67 x + 72 x + 100 x +
33 x + 94, [x], Dom::IntegerMod(101)) x
>> Factored::getType(%)
"unknown"
You may use the function expand which returns the factored
object in expanded form as an element of the factorization ring:
>> expand(f)
12
poly(x + x + 1, [x], Dom::IntegerMod(101))
Example
4The third system function which return elements of
Factored is polylib::sqrfree, which computes
the square-free factorization of polynomials. For example:
>> f := polylib::sqrfree(x^2 + 2*x + 1)
2
(x + 1)
The factorization type, of course, is
"squarefree":
>> Factored::getType(f)
"squarefree"