Opened 12 years ago
Closed 12 years ago
#8268 closed enhancement (fixed)
Improve speed of Christoffel word construction
Reported by: | slabbe | Owned by: | slabbe |
---|---|---|---|
Priority: | major | Milestone: | sage-4.3.4 |
Component: | combinatorics | Keywords: | christoffel words |
Cc: | abmasse | Merged in: | sage-4.3.4.alpha0 |
Authors: | Sébastien Labbé | Reviewers: | Alexandre Blondin Massé |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
This patch adds a new implementation for construction of Christoffel words using continued fraction :
sage: %timeit words.ChristoffelWord(5, 9, algorithm='linear') 625 loops, best of 3: 67.7 µs per loop sage: %timeit words.ChristoffelWord(5, 9, algorithm='cf') 625 loops, best of 3: 309 µs per loop
For large words, it is much faster than the actual implementation.
sage: %timeit words.ChristoffelWord(500, 90001, algorithm='linear') 5 loops, best of 3: 111 ms per loop sage: %timeit words.ChristoffelWord(500, 90001, algorithm='cf') 125 loops, best of 3: 4 ms per loop
Attachments (2)
Change History (9)
Changed 12 years ago by
comment:1 Changed 12 years ago by
- Cc abmasse added
- Status changed from new to needs_review
comment:2 Changed 12 years ago by
comment:3 Changed 12 years ago by
- Keywords christoffel words added
- Reviewers set to Alexandre Blondin Massé
- Status changed from needs_review to positive_review
comment:4 Changed 12 years ago by
- Status changed from positive_review to needs_work
Sorry, forgot two small things, uploading a new patch in a few minutes.
comment:5 Changed 12 years ago by
- Status changed from needs_work to needs_review
comment:6 Changed 12 years ago by
- Status changed from needs_review to positive_review
comment:7 Changed 12 years ago by
- Merged in set to sage-4.3.4.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
Merged in this order:
Note: See
TracTickets for help on using
tickets.
I tested the improved function. It is indeed much faster, especially when the two prime numbers are big. The code makes sense, all tests passed, and I tried also other values with very big prime numbers: no problem. The doc builds fine too.
I made very minor changes (typos, punctuation, etc.). Positive review.