#13346: Add a cython implementation of the Kolakoski word
-----------------------------+----------------------------------------------
Reporter: slabbe | Owner: slabbe
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.3
Component: combinatorics | Keywords:
Work issues: | Report Upstream: N/A
Reviewers: | Authors:
Merged in: | Dependencies:
Stopgaps: |
-----------------------------+----------------------------------------------
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(algorithm='Bernardi')
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
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13346>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
