Opened 6 years ago
Closed 6 years ago
#17319 closed enhancement (fixed)
Add a powers() method to monoid elements
Reported by:  pbruin  Owned by:  

Priority:  minor  Milestone:  sage6.4 
Component:  basic arithmetic  Keywords:  power 
Cc:  Merged in:  
Authors:  Peter Bruin  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  fe3f8f1 (Commits)  Commit:  fe3f8f1133b11344463e0f67a5aeeab2815e5a11 
Dependencies:  Stopgaps: 
Description
The purpose of this ticket is to add a powers()
method to MonoidElement
and RingElement
such that x.powers(n)
returns [x^0, x^1, ..., x^(n1)]
. This only needs n  1 multiplications and hence is more efficient than calling [x^i for i in xrange(n)]
. Examples:
sage: G = SymmetricGroup(4) sage: g = G([2,3,4,1]) sage: g.powers(4) [(), (1,2,3,4), (1,3)(2,4), (1,4,3,2)] sage: 5.powers(3) [1, 5, 25]
Inspired by the powers()
function that was recently added to PARI.
Change History (8)
comment:1 Changed 6 years ago by
 Branch set to u/pbruin/17319powers
 Commit set to 885fd30f187f8b99c13f0eb660dac7c6ee66dc96
 Status changed from new to needs_review
comment:2 followup: ↓ 4 Changed 6 years ago by
 Reviewers set to Travis Scrimshaw
I'm going to be (extremely) paranoid and ask to rewrite x *= self
as x = x * self
in case something happens to get done in place. Otherwise LGTM.
Edit  Actually could you also add it to Monoids.ElementMethods
for monoids whose elements don't inherit from MonoidElement
?
comment:3 Changed 6 years ago by
 Commit changed from 885fd30f187f8b99c13f0eb660dac7c6ee66dc96 to 72d665c754df9440f35299720c6191d601ae695b
Branch pushed to git repo; I updated commit sha1. New commits:
72d665c  Trac 17319: add Monoids.ElementMethods.powers() and use x = x * self

comment:4 in reply to: ↑ 2 Changed 6 years ago by
Replying to tscrim:
I'm going to be (extremely) paranoid and ask to rewrite
x *= self
asx = x * self
in case something happens to get done in place. Otherwise LGTM.
Good point, done.
Edit  Actually could you also add it to
Monoids.ElementMethods
for monoids whose elements don't inherit fromMonoidElement
?
Also done; matrices are an example of this.
comment:6 Changed 6 years ago by
 Commit changed from 72d665c754df9440f35299720c6191d601ae695b to fe3f8f1133b11344463e0f67a5aeeab2815e5a11
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
fe3f8f1  Trac 17319: fix doctests

comment:7 Changed 6 years ago by
 Status changed from needs_review to positive_review
The last addition made two doctests fail, this commit fixes them.
comment:8 Changed 6 years ago by
 Branch changed from u/pbruin/17319powers to fe3f8f1133b11344463e0f67a5aeeab2815e5a11
 Resolution set to fixed
 Status changed from positive_review to closed
The method needs to be added twice because
RingElement
does not inherit fromMonoidElement
. I tried the alternative of adding it toMonoids.ElementMethods
, but this is much slower.