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:  sage6.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: 
Description (last modified by )
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
 Branch set to u/pbruin/17327DirichletCharacter_values
 Commit set to 511c9a507c751129d3003d1c15c9ecca0029b587
 Status changed from new to needs_review
comment:2 Changed 7 years ago by
 Status changed from needs_review to needs_work
comment:3 Changed 7 years ago by
 Commit changed from 511c9a507c751129d3003d1c15c9ecca0029b587 to e6e0c1f37c5cea77d10ef7437f7f829ddcd32c52
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
e6e0c1f  Trac 17327: simplify computation of values of Dirichlet characters

comment:4 Changed 7 years ago by
 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
 Commit changed from e6e0c1f37c5cea77d10ef7437f7f829ddcd32c52 to aa172e37a5b4d42f089d079e9af2ba1506bbcbcf
Branch pushed to git repo; I updated commit sha1. New commits:
aa172e3  Merge branch 'develop' into ticket/17327DirichletCharacter_values

comment:6 Changed 7 years ago by
 Branch changed from u/pbruin/17327DirichletCharacter_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
 Commit changed from aa172e37a5b4d42f089d079e9af2ba1506bbcbcf to f9586a5756d46e9e70bec59d171de07d5b841353
 Milestone changed from sage6.4 to sage6.6
 Reviewers set to Jeroen Demeyer
I made some further improvements...
New commits:
f9586a5  Further simplify values(), use @cached_method

comment:8 Changed 7 years ago by
 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
 Branch changed from u/jdemeyer/ticket/17327 to f9586a5756d46e9e70bec59d171de07d5b841353
 Resolution set to fixed
 Status changed from positive_review to closed
Unfortunately the current version gives a 50% slowdown (from 3 seconds to 4.5 seconds) for the following command:
This seems to be caused by an overdose of Python
map
andlambda
constructions.