#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 | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
---------------------------------+------------------------------------------
Description changed by slabbe:
Old description:
> 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
> }}}
New description:
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
}}}
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13346#comment:1>
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.
