Opened 7 years ago

Closed 7 years ago

#17327 closed enhancement (fixed)

Simplify computation of values of Dirichlet characters

Reported by: pbruin Owned by:
Priority: minor Milestone: sage-6.6
Component: number theory Keywords: Dirichlet characters
Cc: Merged in:
Authors: Peter Bruin, Jeroen Demeyer Reviewers: Jeroen Demeyer, Peter Bruin
Report Upstream: N/A Work issues:
Branch: f9586a5 (Commits, GitHub, GitLab) Commit: f9586a5756d46e9e70bec59d171de07d5b841353
Dependencies: #17317 Stopgaps:

Status badges

Description (last modified by pbruin)

The method DirichletCharacter.values() is rather complicated. The goal of this ticket is to simplify it a bit, and in particular to remove the check for the trivial character. It turns out that checking for the trivial character costs more time than is gained by the faster code for this case. This yields a speedup of about 20% in the following example:

sage: %timeit -n 1 -r 1 -c [[chi.values() for chi in DirichletGroup(n)] for n in xrange(1, 100)]

Change History (9)

comment:1 Changed 7 years ago by pbruin

  • Branch set to u/pbruin/17327-DirichletCharacter_values
  • Commit set to 511c9a507c751129d3003d1c15c9ecca0029b587
  • Status changed from new to needs_review

comment:2 Changed 7 years ago by pbruin

  • Status changed from needs_review to needs_work

Unfortunately the current version gives a 50% slowdown (from 3 seconds to 4.5 seconds) for the following command:

sage: %timeit -n 1 -r 1 -c [[chi.values() for chi in DirichletGroup(n)]
....:                       for n in xrange(1, 100)]

This seems to be caused by an overdose of Python map and lambda constructions.

comment:3 Changed 7 years ago by git

  • Commit changed from 511c9a507c751129d3003d1c15c9ecca0029b587 to e6e0c1f37c5cea77d10ef7437f7f829ddcd32c52

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

e6e0c1fTrac 17327: simplify computation of values of Dirichlet characters

comment:4 Changed 7 years ago by pbruin

  • Dependencies changed from #17317, #17319 to #17317
  • Description modified (diff)
  • Status changed from needs_work to needs_review
  • Type changed from task to enhancement

comment:5 Changed 7 years ago by git

  • Commit changed from e6e0c1f37c5cea77d10ef7437f7f829ddcd32c52 to aa172e37a5b4d42f089d079e9af2ba1506bbcbcf

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

aa172e3Merge branch 'develop' into ticket/17327-DirichletCharacter_values

comment:6 Changed 7 years ago by jdemeyer

  • Branch changed from u/pbruin/17327-DirichletCharacter_values to u/jdemeyer/ticket/17327
  • Created changed from 11/12/14 18:59:36 to 11/12/14 18:59:36
  • Modified changed from 02/18/15 12:54:33 to 02/18/15 12:54:33

comment:7 Changed 7 years ago by jdemeyer

  • Authors changed from Peter Bruin to Peter Bruin, Jeroen Demeyer
  • Commit changed from aa172e37a5b4d42f089d079e9af2ba1506bbcbcf to f9586a5756d46e9e70bec59d171de07d5b841353
  • Milestone changed from sage-6.4 to sage-6.6
  • Reviewers set to Jeroen Demeyer

I made some further improvements...


New commits:

f9586a5Further simplify values(), use @cached_method

comment:8 Changed 7 years ago by pbruin

  • Reviewers changed from Jeroen Demeyer to Jeroen Demeyer, Peter Bruin
  • Status changed from needs_review to positive_review

The additional improvements look good to me, and all doctests pass.

comment:9 Changed 7 years ago by vbraun

  • Branch changed from u/jdemeyer/ticket/17327 to f9586a5756d46e9e70bec59d171de07d5b841353
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.