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: sage-6.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^(n-1)]. 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 pbruin

  • Branch set to u/pbruin/17319-powers
  • Commit set to 885fd30f187f8b99c13f0eb660dac7c6ee66dc96
  • Status changed from new to needs_review

The method needs to be added twice because RingElement does not inherit from MonoidElement. I tried the alternative of adding it to Monoids.ElementMethods, but this is much slower.

comment:2 follow-up: Changed 6 years ago by tscrim

  • 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?

Last edited 6 years ago by tscrim (previous) (diff)

comment:3 Changed 6 years ago by git

  • Commit changed from 885fd30f187f8b99c13f0eb660dac7c6ee66dc96 to 72d665c754df9440f35299720c6191d601ae695b

Branch pushed to git repo; I updated commit sha1. New commits:

72d665cTrac 17319: add Monoids.ElementMethods.powers() and use x = x * self

comment:4 in reply to: ↑ 2 Changed 6 years ago by pbruin

Replying to tscrim:

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.

Good point, done.

Edit - Actually could you also add it to Monoids.ElementMethods for monoids whose elements don't inherit from MonoidElement?

Also done; matrices are an example of this.

comment:5 Changed 6 years ago by tscrim

  • Status changed from needs_review to positive_review

Thanks!

comment:6 Changed 6 years ago by git

  • 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:

fe3f8f1Trac 17319: fix doctests

comment:7 Changed 6 years ago by pbruin

  • 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 vbraun

  • Branch changed from u/pbruin/17319-powers to fe3f8f1133b11344463e0f67a5aeeab2815e5a11
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.