Opened 10 years ago
Closed 10 years ago
#13166 closed enhancement (fixed)
Compute q-binomial coefficients more efficiently
Reported by: | Armin Straub | Owned by: | Sage Combinat CC user |
---|---|---|---|
Priority: | minor | Milestone: | sage-5.2 |
Component: | combinatorics | Keywords: | |
Cc: | Merged in: | sage-5.2.beta1 | |
Authors: | Armin Straub | Reviewers: | Javier López Peña |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Currently, q-binomials are calculated as a fraction of products of q-integers. With the attached patch, q-binomials are computed as a product of cyclotomic polynomials. This avoids reducing a fraction of polynomials and is significantly faster for larger q-binomial coefficients.
Before:
sage: from sage.combinat.q_analogues import * sage: %timeit q_binomial(18,7) 125 loops, best of 3: 1.89 ms per loop sage: %timeit q_binomial(180,70) 5 loops, best of 3: 1.4 s per loop
After:
sage: from sage.combinat.q_analogues import * sage: %timeit q_binomial(18,7) 125 loops, best of 3: 2.01 ms per loop sage: %timeit q_binomial2(180,70) 25 loops, best of 3: 34.7 ms per loop
Apply trac_13166_q_binomials.patch and trac_13166_q_binomials_reference.patch
Attachments (2)
Change History (10)
Changed 10 years ago by
Attachment: | trac_13166_q_binomials.patch added |
---|
comment:1 Changed 10 years ago by
Description: | modified (diff) |
---|
comment:2 Changed 10 years ago by
Status: | new → needs_review |
---|
comment:3 Changed 10 years ago by
Reviewers: | → Javier López Peña |
---|
comment:4 Changed 10 years ago by
patchbot: apply trac_13166_q_binomials.patch trac_13166.reviewer.patch
Changed 10 years ago by
Attachment: | trac_13166_q_binomials_reference.patch added |
---|
comment:5 Changed 10 years ago by
Thank you for adding a reference!
I was trying to understand how docstrings in general are working... based on what I saw in other files, I have slightly modified your documentation (for instance, no double colon after REFERENCES and an underscore when citing the reference). Please correct me if this is wrong.
Other than this nitpicking, I am happy with your addition.
comment:6 Changed 10 years ago by
patchbot: apply trac_13166_q_binomials.patch trac_13166_q_binomials_reference.patch
comment:7 Changed 10 years ago by
Description: | modified (diff) |
---|---|
Status: | needs_review → positive_review |
You are correct, I tend to mess up the markup every now and then... ;-) Code still looks good, test still pass, and patchbot seems happy, so positive review!
comment:8 Changed 10 years ago by
Merged in: | → sage-5.2.beta1 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
Nice! Code looks good, all tests pass. I have added a reference for the new method in the documentation, if you agree with my reviewer patch you can give this a positive review.