Previous Page Next Page Contents

Factored -- the domain of objects kept in factored form

Introduction

Factored 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 Elements

Factored(list <, type> <, ring>)
Factored(f <, type> <, ring>)

Parameters

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())

Details

Operands

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.

Important Operations

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).

Result of Evaluation

Evaluating an object of type Factored returns itself.

Function Call

Calling a factored object as a function yields the object itself, regardless of the arguments. The arguments are not evaluated.

Method _mult: multiply factored objects

Method _power: raise a factored object to a certain power

Method expand: expand a factored object

Method exponents: get the exponents of a factored object

Method factor: factorize a factored object

Method factors: get the factors of a factored object

Method irreducible: test if a factored object is irreducible

Method iszero: test on zero for factored objects

Method sqrfree: compute a square-free factorization of a factored object

Method _index: extract an operand of a factored object

Method getRing: get the ring of factorization

Method getType: get the type of factorization

Method has: existence of an object in a factored object

Method map: map a function to the operands of factored objects

Method nops: the number of operands of a factored object

Method op: extract an operand of a factored object

Method select: select operands of a factored object

Method set_index: set an operand of a factored object

Method setRing: set the ring of factorization

Method setType: set the type of factorization

Method subs: substitute subexpressions in the operands of a factored object

Method subsop: substitute operands of a factored object

Method type: expression type of factored objects

Method convert: convert an object into a factored object

Method convert_to: convert factored objects into other domains

Method create: create simple and fast a factored objects

Method expr: convert a factored object into a kernel domain

Method expr2text: convert a factored object into a string

Method testtype: type testing for factored objects

Method TeX: LaTeX formatting of a factored object

Method _concat: concatenate operands of factored objects

Method maprec: allow recursive mapping for factored objects

Method print: pretty-print routine for factored objects

Method unapply: create a procedure from a factored object

Example 1

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.

Example 2

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

Example 3

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))

Example 4

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"

Changes




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000