Ticket #8268 (closed enhancement: fixed)

Opened 3 years ago

Last modified 3 years ago

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 Work issues:
Report Upstream: N/A Reviewers: Alexandre Blondin Massé
Authors: Sébastien Labbé Merged in: sage-4.3.4.alpha0
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

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

Change History

Changed 3 years ago by slabbe

comment:1 Changed 3 years ago by slabbe

  • Cc abmasse added
  • Status changed from new to needs_review

comment:2 Changed 3 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 3 years ago by abmasse

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

comment:4 Changed 3 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 3 years ago by abmasse

  • Status changed from needs_work to needs_review

Changed 3 years ago by abmasse

Minor change -- apply on top

comment:6 Changed 3 years ago by abmasse

  • Status changed from needs_review to positive_review

comment:7 Changed 3 years ago by mvngu

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

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.