id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
13346,Add a cython implementation of the Kolakoski word,slabbe,slabbe,"A Python implementation of the Kolakoski word was implemented some time ago in #8739. But, there exist much faster implementation especially some lines of C code of Dominique Bernardi shared by himself during Sage Days 28 in Orsay, France, in January 2011.
This patch adds a cython version of the code of Bernardi. It is much faster than the actual python implementation in Sage.
BEFORE:
{{{
sage: K = words.KolakoskiWord()
sage: K
word: 1221121221221121122121121221121121221221...
sage: time K[100000]
1
Time: CPU 0.96 s, Wall: 1.36 s
sage: time K[1000000] # takes forever
}}}
AFTER:
{{{
sage: K = words.KolakoskiWord()
sage: K
word: 1221121221221121122121121221121121221221...
sage: time K[1000000]
2
Time: CPU 0.01 s, Wall: 0.02 s
sage: time K[100000000]
1
Time: CPU 1.38 s, Wall: 1.92 s
}}}",enhancement,needs_work,major,sage-6.4,combinatorics,,,abmasse tjolivet,,,,N/A,,,,#12224,