Opened 8 years ago

Last modified 6 years ago

#13346 needs_work enhancement

Add a cython implementation of the Kolakoski word

Reported by: slabbe Owned by: slabbe
Priority: major Milestone: sage-6.4
Component: combinatorics Keywords:
Cc: abmasse, tjolivet Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12224 Stopgaps:

Description (last modified by 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                     

Attachments (1)

trac13346_kolakoski_cython-sl.patch (15.4 KB) - added by slabbe 8 years ago.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 8 years ago by slabbe

  • Description modified (diff)

comment:2 Changed 8 years ago by slabbe

  • Cc ablondin added
  • Status changed from new to needs_review

comment:3 Changed 8 years ago by slabbe

  • Cc abmasse added; ablondin removed

Changed 8 years ago by slabbe

comment:4 Changed 8 years ago by slabbe

I just updated the patch.

comment:5 Changed 7 years ago by slabbe

  • Cc tjolivet added

comment:6 Changed 7 years ago by abmasse

I should work on this ticket in the next days. I just need to install the newest sage version.

comment:7 Changed 7 years ago by slabbe

Salut Alex,

En fait, un patch de V. Delecroix et Stepan Starosta est en attente et mon ticket ne s'applique plus sur le leur... Je devrais écrire une nouvelle version au courant de la semaine prochaine si tout va bien... Donc, le review de ce ticket est en stand by pour l'instant.

Oups, I wrote in French sorry.

Sébastien

comment:8 Changed 7 years ago by slabbe

  • Dependencies set to #12224
  • Status changed from needs_review to needs_work

This ticket needs work to give the opportunity to #12224 to get into Sage first. Hoping it will not take forever.

comment:9 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:10 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:11 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:12 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.