#15236: Let Sage use finite fields without primality proving
-------------------------------------------------+-------------------------
Reporter: jpflori | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.0
Component: finite rings | Resolution:
Keywords: finite fields, primality | Merged in:
proving, sd53 | Reviewers:
Authors: | Work issues:
Report Upstream: N/A | Commit:
Branch: | Stopgaps:
Dependencies: |
-------------------------------------------------+-------------------------
Comment (by SimonKing):
Concerning things that may be slower: Practical examples can probably by
found on #11900.
__Raw timings in Python__
{{{
sage: class PyRing(Parent):
....: def is_field(self):
....: return False
....:
sage: class PyField(Parent):
....: def is_field(self):
....: return True
....:
sage: TrueRing = PyRing(category=Rings())
sage: RingInFields = PyRing(category=Fields())
sage: MockField = PyField(category=Rings())
sage: TrueField = PyField(category=Fields())
sage: F = Fields()
}}}
A ring that is not a field:
{{{
sage: TrueRing in F
False
sage: %timeit TrueRing in F
100000 loops, best of 3: 2.07 us per loop
sage: %timeit TrueRing.is_field()
1000000 loops, best of 3: 291 ns per loop
}}}
A ring that is put into the category of fields. Hence, `R in Fields()` and
`R.is_field()` give different answers. I am doing this just for
completeness:
{{{
sage: %timeit RingInFields in F
1000000 loops, best of 3: 821 ns per loop
sage: %timeit RingInFields.is_field()
1000000 loops, best of 3: 287 ns per loop
}}}
A field that is only initialised in the category of rings. Note that
because `.is_field()` returns True and because of the way how
`Fields.__contains__` works, the category is refined after the first
containment test:
{{{
sage: MockField.category()
Category of rings
sage: MockField in F
True
sage: MockField.category()
Category of fields
sage: %timeit MockField in F
1000000 loops, best of 3: 823 ns per loop
sage: %timeit MockField.is_field()
1000000 loops, best of 3: 312 ns per loop
}}}
And finally, a field that is a field that is a field...
{{{
sage: %timeit TrueField in F
1000000 loops, best of 3: 819 ns per loop
sage: %timeit TrueField.is_field()
1000000 loops, best of 3: 309 ns per loop
}}}
__Raw timings in Cython__
We construct similar examples as above, both for Python classes in Cython
and for "real" extension classes. So, we have eight examples.
{{{
sage: cython("""
....: from sage.structure.parent cimport Parent
....: class CyRing(Parent):
....: def is_field(self):
....: return False
....: class CyField(Parent):
....: def is_field(self):
....: return True
....: cdef class ExtRing(Parent):
....: def is_field(self):
....: return False
....: cdef class ExtField(Parent):
....: def is_field(self):
....: return True
....: """)
}}}
First, the Python classes defined in Cython:
{{{
sage: TrueRing = CyRing(category=Rings())
sage: RingInFields = CyRing(category=Fields())
sage: MockField = CyField(category=Rings())
sage: TrueField = CyField(category=Fields())
sage: %timeit TrueRing in F
1000000 loops, best of 3: 1.85 us per loop
sage: %timeit TrueRing.is_field()
1000000 loops, best of 3: 236 ns per loop
sage: %timeit RingInFields in F
1000000 loops, best of 3: 850 ns per loop
sage: %timeit RingInFields.is_field()
1000000 loops, best of 3: 250 ns per loop
sage: %timeit MockField in F
1000000 loops, best of 3: 846 ns per loop
sage: %timeit MockField.is_field()
1000000 loops, best of 3: 252 ns per loop
sage: %timeit TrueField in F
1000000 loops, best of 3: 852 ns per loop
sage: %timeit TrueField.is_field()
1000000 loops, best of 3: 231 ns per loop
}}}
And finally the extension classes:
{{{
sage: TrueRing = ExtRing(category=Rings())
sage: RingInFields = ExtRing(category=Fields())
sage: MockField = ExtField(category=Rings())
sage: TrueField = ExtField(category=Fields())
sage: %timeit TrueRing in F
1000000 loops, best of 3: 1.81 us per loop
sage: %timeit TrueRing.is_field()
10000000 loops, best of 3: 166 ns per loop
sage: %timeit RingInFields in F
1000000 loops, best of 3: 826 ns per loop
sage: %timeit RingInFields.is_field()
10000000 loops, best of 3: 162 ns per loop
sage: %timeit MockField in F
1000000 loops, best of 3: 845 ns per loop
sage: %timeit MockField.is_field()
10000000 loops, best of 3: 163 ns per loop
sage: %timeit TrueField in F
1000000 loops, best of 3: 836 ns per loop
sage: %timeit TrueField.is_field()
10000000 loops, best of 3: 167 ns per loop
}}}
__Remark__
Testing containment in other singleton categories is faster then testing
in Fields():
{{{
sage: TrueField = PyField(category=Fields())
sage: %timeit TrueField in R
1000000 loops, best of 3: 358 ns per loop
sage: TrueField = CyField(category=Fields())
sage: %timeit TrueField in R
1000000 loops, best of 3: 362 ns per loop
sage: TrueField = ExtField(category=Fields())
sage: %timeit TrueField in R
1000000 loops, best of 3: 352 ns per loop
}}}
__Conclusion__
I think the timings clearly show that `is_field()` is always faster by a
factor of more than two and often an even bigger factor. There might be a
slow-down, however, because one should wrap `R.is_field()` into a `try:
... except AttributeError: ...` statement.
--
Ticket URL: <http://trac.sagemath.org/ticket/15236#comment:5>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
