Factored
-- the domain of
objects kept in factored formFactored
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.
Factored(list <, type> <, ring>)
Factored(f <, type> <, ring>)
list |
- | a list of odd length |
f |
- | an arithmetical expression |
type |
- | a string (default:
"unknown" ) |
ring |
- | a domain of category Cat::IntegralDomain (default:
Dom::ExpressionField() ) |
list
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.The 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.
We 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
The 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))
The 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"