Improve speed of Christoffel word construction

[seblabbe]

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

CC: @sagetrac-abmasse

Component: combinatorics

Keywords: christoffel words

Author: Sébastien Labbé

Reviewer: Alexandre Blondin Massé

Merged: sage-4.3.4.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/8268

[seblabbe]

comment:1

Attachment: trac_8268_speed_up_Christoffel-sl.patch.gz

[sagetrac-abmasse]

comment:2

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.

[sagetrac-abmasse]

Author: Sébastien Labbé

[sagetrac-abmasse]

Changed keywords from none to christoffel words

[sagetrac-abmasse]

Reviewer: Alexandre Blondin Massé

[sagetrac-abmasse]

comment:4

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

[sagetrac-abmasse]

Minor change -- apply on top

[sagetrac-abmasse]

comment:6

Attachment: trac_8268_review-abm.patch.gz

[sagetrac-mvngu]

Merged: sage-4.3.4.alpha0

[sagetrac-mvngu]

comment:7

Merged in this order:

1. trac_8268_speed_up_Christoffel-sl.patch
2. trac_8268_review-abm.patch