Opened 7 years ago

Closed 7 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)

trac_8268_speed_up_Christoffel-sl.patch​ (3.5 KB) - added by slabbe 7 years ago.
trac_8268_review-abm.patch​ (2.0 KB) - added by abmasse 7 years ago.
Minor change -- apply on top

Download all attachments as: .zip

Change History (9)

Changed 7 years ago by slabbe

comment:1 Changed 7 years ago by slabbe

  • Cc abmasse added
  • Status changed from new to needs_review

comment:2 Changed 7 years ago by abmasse

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.

comment:3 Changed 7 years ago by abmasse

  • Authors set to Sébastien Labbé
  • Keywords christoffel words added
  • Reviewers set to Alexandre Blondin Massé
  • Status changed from needs_review to positive_review

comment:4 Changed 7 years ago by abmasse

  • Status changed from positive_review to needs_work

Sorry, forgot two small things, uploading a new patch in a few minutes.

comment:5 Changed 7 years ago by abmasse

  • Status changed from needs_work to needs_review

Changed 7 years ago by abmasse

Minor change -- apply on top

comment:6 Changed 7 years ago by abmasse

  • Status changed from needs_review to positive_review

comment:7 Changed 7 years ago by mvngu

  • Merged in set to sage-4.3.4.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

Merged in this order:

  1. ​trac_8268_speed_up_Christoffel-sl.patch
  2. ​trac_8268_review-abm.patch
Note: See TracTickets for help on using tickets.