#10184: class group iterator is too slow
----------------------------------+------------------------------
Reporter: thome | Owner: davidloeffler
Type: enhancement | Status: needs_work
Priority: minor | Milestone:
Component: number fields | Resolution:
Keywords: | Merged in:
Authors: Emmanuel Thome | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Dependencies:
Stopgaps: |
----------------------------------+------------------------------
Changes (by {'newvalue': u'Emmanuel Thome', 'oldvalue': ''}):
* author: => Emmanuel Thome
Old description:
> the class group iterator takes evey element in turn, and computes the
> product of the g^i's. Sure powers are computed by repeated squaring, but
> for iterators this is suboptimal.
>
> On my laptop, from this situation...
>
> {{{
>
> sage: K.<v>=NumberField(x^4 + 514*x^2 + 64321)
> sage: OK=K.maximal_order()
> sage: G=K.class_group()
> sage: time _=G.list()
> CPU times: user 2.48 s, sys: 0.05 s, total: 2.53 s
> Wall time: 2.53 s
>
> }}}
>
> the attached patch improves to...
>
> {{{
>
> sage: K.<v>=NumberField(x^4 + 514*x^2 + 64321)
> sage: OK=K.maximal_order()
> sage: G=K.class_group()
> sage: time _=G.list()
> CPU times: user 0.45 s, sys: 0.00 s, total: 0.45 s
> Wall time: 0.44 s
>
> }}}
>
> which is a tad better.
>
> doctest included (actually the previous doctest wasn't doing much, this
> one is slightly more thorough).
>
> Note: while the code would work for any abelian group, I believe it makes
> sense only when the group operation is sufficiently non-trivial.
New description:
the class group iterator takes evey element in turn, and computes the
product of the {{{g^i}}}'s. Sure powers are computed by repeated squaring,
but for iterators this is suboptimal.
On my laptop, from this situation...
{{{
sage: K.<v>=NumberField(x^4 + 514*x^2 + 64321)
sage: OK=K.maximal_order()
sage: G=K.class_group()
sage: time _=G.list()
CPU times: user 2.48 s, sys: 0.05 s, total: 2.53 s
Wall time: 2.53 s
}}}
the attached patch improves to...
{{{
sage: K.<v>=NumberField(x^4 + 514*x^2 + 64321)
sage: OK=K.maximal_order()
sage: G=K.class_group()
sage: time _=G.list()
CPU times: user 0.45 s, sys: 0.00 s, total: 0.45 s
Wall time: 0.44 s
}}}
which is a tad better.
doctest included (actually the previous doctest wasn't doing much, this
one is slightly more thorough).
Note: while the code would work for any abelian group, I believe it makes
sense only when the group operation is sufficiently non-trivial.
--
--
Ticket URL: <http://trac.sagemath.org/ticket/10184#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.
