#10771: gcd and lcm for fraction fields
--------------------------------+-------------------------------------------
Reporter: SimonKing | Owner: AlexGhitza
Type: defect | Status: needs_work
Priority: major | Milestone: sage-4.7
Component: basic arithmetic | Keywords: gcd lcm fraction fields
Author: Simon King | Upstream: N/A
Reviewer: Marco Streng | Merged:
Work_issues: |
--------------------------------+-------------------------------------------
Comment(by SimonKing):
Hi Luis!
Replying to [comment:11 lftabera]:
> > That's implemented as element methods for the category of `Fields()`.
Somehow, the category framework is cool, isn't it?
>
> I do not full understand this, but I am happy that works.
Then let me explain:
Any category (in Sage) comes with a parent class and an "element class".
That very often is an abstract thing, but you can inherit from it, and in
particular you can implement methods for it.
If things are properly done, then a parent P is declared as an object in
some category, and its class ''automatically(!)'' inherits from the parent
class of its category:
{{{
sage: QQ.__class__
<class 'sage.rings.rational_field.RationalField_with_category'>
sage: issubclass(QQ.__class__,QuotientFields().parent_class)
True
}}}
If things are very properly done, then the parent has an attribute
`Element`, which is supposed to be a class. That class will (again
automatically) be translated into a subclass of the element class of the
parent's category, and is available as the attribute `element_class`:
{{{
sage: m = matrix(GF(2),[[1]])
sage: G = MatrixGroup([m])
sage: G.Element
<class 'sage.groups.matrix_gps.matrix_group_element.MatrixGroupElement'>
sage: G.__class__
<class
'sage.groups.matrix_gps.matrix_group.MatrixGroup_gens_finite_field_with_category'>
sage: G.element_class
<class
'sage.groups.matrix_gps.matrix_group_element.MatrixGroup_gens_finite_field_with_category.element_class'>
sage: issubclass(G.element_class,G.Element)
True
sage: issubclass(G.element_class,G.category().element_class)
True
sage: isinstance(G.random_element(),G.category().element_class)
True
}}}
So, if things are very properly done, then a method defined as an "element
method" of a category, will be available by looking up the method
resolution order, since the elements of the parent are actual instances of
the category's element class.
Sometimes things are done properly, but not ''very'' properly:
{{{
sage: QQ.category()
Category of quotient fields
sage: isinstance(QQ, QQ.category().parent_class)
True
sage: hasattr(QQ,'Element')
False
sage: isinstance(QQ.one(), QQ.category().element_class)
False
}}}
Hence, the methods that I defined for the element class of the "category
of quotient fields" is not available to elements of `QQ` by simply looking
up the method resolution order. But: There also is a `__getattr__` method
implemented for `sage.structure.element.Element`, and this can access the
element methods of the category of the parent of an element (uff!) even if
the element is no instance of the "proper" element class.
This is why the new gcd works for the rationals, but it's slower than with
the method resolution order, and this is why I also did not remove the
existing lcm for rationals.
> Some thoughts:
>
> For QQ and the like, could it be that gcd and lcm should only take care
of coercing to a good setting and then the real algorithm should be in
_lcm, _gcd? Note that QQ already has ._gcd and ._lcm so these methods has
to be taken into account.
That's a nice observation. By searching a little, I found that `_gcd` is
used in the method
`sage.structure.element.PrincipalIdealDomainElement.gcd`.
However, there are only very few classes that define a `_gcd` method:
`sage.structure.element.EuclideanDomainElement`,
`sage.structure.element.FieldElement`, `sage.rings.rational.Rational`, and
then there are hits in `...polynomial_element_generic` and
`...polynomial_modn_dense_ntl`.
In other words, I guess that the `_gcd` method is an artefact of earlier
attempts to reflect mathematics in the class hierarchy -- this should now
be done in the category framework. `_gcd` will ''only'' play a role if
1. the class of an element derives from `PrincipalIdealDomainElement`,
and
2. the class of an element additionally defines `_gcd`.
It seems to me that there is precisely one class that directly inherits
from `PrincipalIdealDomainElement`, and there is precisely one class that
directly inherits from that class:
{{{
sage: search_src("\(PrincipalIdealDomainElement")
structure/element.pxd:83:cdef class
EuclideanDomainElement(PrincipalIdealDomainElement):
structure/element.pyx:2370:cdef class
EuclideanDomainElement(PrincipalIdealDomainElement):
sage: search_src("\(EuclideanDomainElement")
structure/element.pyx:2362:PY_SET_TP_NEW(EuclideanDomainElement, Element)
rings/integer.pxd:9:cdef class Integer(EuclideanDomainElement):
}}}
So, `_gcd` is only used for the `Integer` class. I guess it could easily
be removed.
> For generic Fields, It should appear in the documentation that the
methods return 0 if both arguments are zero and a non-zero element
otherwise. The user should not suppose that the non-zero element is
actually one, since this is changed by subclasses.
Right. I'll take care of that, but now I have a bus to catch...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10771#comment:12>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
