#18547: Improve polynomial powering in positive characteristic
-------------------------------------+-------------------------------------
Reporter: bruno | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.9
Component: commutative | Resolution:
algebra | Merged in:
Keywords: polynomial, | Reviewers:
powering | Work issues:
Authors: Bruno Grenet | Commit:
Report Upstream: N/A | 5a4965ccb5a4b03b5abcca65d0daeb4a96190a58
Branch: | Stopgaps:
u/bruno/polynomial_powering_positive_characteristic|
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by bruno):
Replying to [comment:18 jdemeyer]:
> Please justify in the code why
> {{{
> # characteristic 2 is special
> }}}
I had run some tests and my conclusion that was using `generic_power` was
faster in characteristic 2. (Note that binary exponentiation is well
suited to this characteristic.) I am not able to reproduce this behavior
though, so I removed the special case.
Replying to [comment:20 jdemeyer]:
> And I'm not too happy with this either:
> {{{
> self.base_ring().is_field()
> }}}
>
> Checking whether some complicated ring is a field might be an expensive
operation. I prefer
> {{{
> self.base_ring() in IntegralDomains
> }}}
Done.
Replying to [comment:19 jdemeyer]:
> I suggest to remove the special case for finite fields. The generic code
should work just fine for finite fields.
Actually, the current code is faster for finite fields. With the special
case:
{{{#!python
sage: R.<x> = PolynomialRing(GF(17),sparse=True)
sage: p = R.random_element(100)
sage: %timeit p^(17^5)
The slowest run took 11.13 times longer than the fastest. This could mean
that an intermediate result is being cached
1000 loops, best of 3: 159 µs per loop
}}}
Without the special case, with the same `p`:
{{{#!python
%timeit p^(17^5)
The slowest run took 26.59 times longer than the fastest. This could mean
that an intermediate result is being cached
1000 loops, best of 3: 249 µs per loop
}}}
I may refactor the code though so that it is less redundant. Tell me what
you think.
Replying to [comment:17 jdemeyer]:
> I think this test is much too weak
I am happy if you find a good way to test this function!
--
Ticket URL: <http://trac.sagemath.org/ticket/18547#comment:23>
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/d/optout.
