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:

Status badges

Description (last modified by jlopez)

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)

trac_13166_q_binomials.patch (1.3 KB) - added by Armin Straub 10 years ago.
trac_13166_q_binomials_reference.patch (1005 bytes) - added by Armin Straub 10 years ago.

Download all attachments as: .zip

Change History (10)

Changed 10 years ago by Armin Straub

comment:1 Changed 10 years ago by Armin Straub

Description: modified (diff)

comment:2 Changed 10 years ago by Armin Straub

Status: newneeds_review

comment:3 Changed 10 years ago by jlopez

Reviewers: Javier López Peña

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.

comment:4 Changed 10 years ago by jlopez

patchbot: apply trac_13166_q_binomials.patch trac_13166.reviewer.patch

Changed 10 years ago by Armin Straub

comment:5 Changed 10 years ago by Armin Straub

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 Armin Straub

patchbot: apply trac_13166_q_binomials.patch trac_13166_q_binomials_reference.patch

comment:7 Changed 10 years ago by jlopez

Description: modified (diff)
Status: needs_reviewpositive_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 Jeroen Demeyer

Merged in: sage-5.2.beta1
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.