Create a new module for morphic words

[sagetrac-jlepsova]

The goal of this ticket is to create a new module for morphic words.

As a consequence, it will improve the following computations which take a lot of time:

sage: m = WordMorphism('a->ab,b->a')
sage: w = m.fixed_point('a')
sage: w
word: abaababaabaababaababaabaababaabaababaaba...
sage: %time w[1000]
CPU times: user 1.45 ms, sys: 0 ns, total: 1.45 ms
Wall time: 1.45 ms
'a'
sage: %time w[10000]
CPU times: user 82.9 ms, sys: 0 ns, total: 82.9 ms
Wall time: 82.1 ms
'a'
sage: %time w[100000]
CPU times: user 5.19 s, sys: 6.26 ms, total: 5.2 s
Wall time: 5.19 s
'b'
sage: %time w[1000000]
CPU times: user 12min 45s, sys: 93.4 ms, total: 12min 45s
Wall time: 12min 45s
'a'

CC: @videlec

Component: combinatorics

Author: Jana Lepšová, Sébastien Labbé

Branch/Commit: 016f022

Reviewer: Vincent Delecroix

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

[fchapoton]

comment:1

duplicate of #31370 ?

[seblabbe]

comment:3

Replying to @fchapoton:

duplicate of #31370 ?

Let's close #31370 and keep this one (Jana is learning how to contribute to Sage).

[seblabbe]

Changed branch from u/jlepsova/morphic to u/slabbe/31378

[seblabbe]

Changed commit from 7876b86 to 86990a0

[seblabbe]

comment:4

I rebased the branch on top of 9.3.beta7. I also added a commit which links the new module added by Jana to the existing sage words library.

---

New commits:

77c4645	adding more efficient way of stating a letter at an n-th position of a fixed point
86990a0	linking morphic.py file to the sage words library

[seblabbe]

comment:5

Jana, the next step is to update the examples in the documentation in the morphic.py file.

With the current branch,

$ sage -bt src/sage/combinat/words/morphic.py 

returns

[...]

**********************************************************************
File "src/sage/combinat/words/morphic.py", line 157, in sage.combinat.words.morphic.WordDatatype_morphic.__iter__
Failed example:
    print('update the examples here')
Expected nothing
Got:
    update the examples here
**********************************************************************

[...]

**********************************************************************
3 items had failures:
   1 of   2 in sage.combinat.words.morphic
   1 of   2 in sage.combinat.words.morphic.WordDatatype_morphic.__getitem__
   6 of  13 in sage.combinat.words.morphic.WordDatatype_morphic.__iter__
    [30 tests, 8 failures, 0.02 s]
----------------------------------------------------------------------
sage -t --warn-long 72.7 --random-seed=0 src/sage/combinat/words/morphic.py  # 8 doctests failed
----------------------------------------------------------------------

[sagetrac-jlepsova]

Changed branch from u/slabbe/31378 to u/jlepsova/morphic

[sagetrac-jlepsova]

Changed commit from 86990a0 to d4e7081

[sagetrac-jlepsova]

comment:6

I fixed the doctests in morphic.py.

---

New commits:

6587375	adding more efficient way of stating a letter at an n-th position of a fixed point
20ae22e	linking morphic.py file to the sage words library
a1f4143	31378: incomplete changes
d4e7081	fixed doctests in morphic.py

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b8690fc

fixing some of the errors in word.py

[sagetrac-git]

Changed commit from d4e7081 to b8690fc

[mkoeppe]

comment:8

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.

[seblabbe]

New commits:

76fcfd6	Merge branch 'u/jlepsova/morphic' into 9.3.rc0
9573c34	31378: fixing doctests in word.py

[seblabbe]

Changed branch from u/jlepsova/morphic to u/slabbe/31378

[seblabbe]

Changed commit from b8690fc to 9573c34

[seblabbe]

comment:10

I fixed the doctests with respect to saving the objects (loads, dumps, reduce, etc.).

It remains only one issue:

            sage: m = WordMorphism("a->ab,b->")          
            sage: w = m.fixed_point("a")                                      
            sage: w.representation(0)                
            []                                      
            sage: w.representation(1)             
            [1]                         
            sage: w.representation(2)  #infinite loop

Jana: can you take a look at this?

[seblabbe]

Author: Jana Lepšová, Sébastien Labbé

[sagetrac-jlepsova]

Changed commit from 9573c34 to ec5d4a7

[sagetrac-jlepsova]

New commits:

cc41397	Merge branch 'u/slabbe/31378' into 9.3.rc3
ec5d4a7	trying to repair the finite fixed point problem, something changed in word_infinite_datatypes.py, however

[sagetrac-jlepsova]

Changed branch from u/slabbe/31378 to u/jlepsova/morphic

[seblabbe]

comment:13

Does the most recent commit also handles the following infinite loop?

sage: m = WordMorphism("a->ab,b->,c->cdab,d->dcab")
sage: w = m.fixed_point("a")
sage: w.representation(2)

What is the remaining problem you mention in the commit message? Can you provide an example?

In the following, the multiplication vMk*M is computed twice. Maybe you want to write vMk1 = vMk*M to represent vM^{k+1} and at the end of the loop, you may do vMk = vMk1.

         while vMk[position] <= n:
+            if vMk == vMk*M:
+                raise ValueError('The morphism has a finite fixed point of length {}.'.format(vMk[position]))
             vMk = vMk*M
             length_of_images.append(vMk)

I would suggest that the error message also include the value of n. Something like IndexError: index (=2) out of range, the fixed point is finite and has length 2.

I think the error should be an IndexError instead of ValueError, as it is for strings:

sage: s = 'ab'                                                                  
sage: s[2]                                                                      
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-2-2d1d9bdb9b26> in <module>
----> 1 s[Integer(2)]

IndexError: string index out of range

[videlec]

comment:30

Are you sure that Computing the n-th letter of a fixed point is fast? If the morphism is primitive then I agree but otherwise...

[videlec]

comment:31

Here is an example

sage: s = WordMorphism('0->011,1->1')
sage: w = s.fixed_point('0')
sage: w # very stupid word :-)
word: 0111111111111111111111111111111111111111...
sage: w.representation(1000000) # now you can wait !!

EDIT: Computing the representation is long (because the answer is long) but computing w[1000000] should be fast.

[videlec]

comment:32

More generally, when the growth of |sigma^n(letter)| is polynomial (and not exponential) then going via the representation is not a good idea.

[seblabbe]

comment:33

Replying to @videlec:

More generally, when the growth of |sigma^n(letter)| is polynomial (and not exponential) then going via the representation is not a good idea.

Well if the growth rate of the |sigma^n(letter)| is quadratic this ticket does an improvement. Here is an example:

On 9.5.beta0:

sage: s = WordMorphism('a->abc,b->bc,c->c')                                     
sage: w = s.fixed_point('a')                                                    
sage: %time w[1000000]                                                          
CPU times: user 6.45 s, sys: 11.5 ms, total: 6.46 s
Wall time: 6.46 s
'c'

On 9.5.beta0 + #31378:

sage: s = WordMorphism('a->abc,b->bc,c->c')                                     
sage: w = s.fixed_point('a')                                                    
sage: %time w[1000000]                                                          
CPU times: user 28.5 ms, sys: 51 µs, total: 28.6 ms
Wall time: 28.4 ms
'c'

Here it grows quadratically:

sage: for i in range(10): u = s('a', i); print(len(u), u)                       
1 a
3 abc
6 abcbcc
10 abcbccbccc
15 abcbccbcccbcccc
21 abcbccbcccbccccbccccc
28 abcbccbcccbccccbcccccbcccccc
36 abcbccbcccbccccbcccccbccccccbccccccc
45 abcbccbcccbccccbcccccbccccccbcccccccbcccccccc
55 abcbccbcccbccccbcccccbccccccbcccccccbccccccccbccccccccc

The problem is when the images grow linearly. Question: can we detect that?

[videlec]

comment:34

The answer is yes, see #32594.

We can do that later on.

[videlec]

comment:35

Sorry : you should fix trailing whitespaces.

[videlec]

Work Issues: trailing whitespaces

[sagetrac-git]

Changed commit from 79c2834 to 29278b4

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

29278b4

31378: removing trailing whitespaces in morphic.py file

[seblabbe]

Changed work issues from trailing whitespaces to none

[seblabbe]

Reviewer: Vincent Delecroix

[seblabbe]

comment:38

I think the issue with trailing whitespaces was mainly with file morphic.py. I removed those from that file.

[videlec]

comment:39

there are more in morphism.py.

[seblabbe]

comment:40

Do you want me to remove all of the trailing whitespaces in the file, or only those in lines that were changed?

[videlec]

comment:41

That is fine with me either way.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

016f022

31378: removing trailing whitespaces in morphism.py

[sagetrac-git]

Changed commit from 29278b4 to 016f022

[seblabbe]

comment:43

I fixed the 2 trailing whitespaces in the file morphism.py that were added in previous commit on this ticket.

[vbraun]

Changed branch from u/slabbe/31378 to 016f022