Opened 3 months ago
Last modified 4 days ago
#31378 needs_review enhancement
Create a new module for morphic words
Reported by:  jlepsova  Owned by:  

Priority:  major  Milestone:  sage9.4 
Component:  combinatorics  Keywords:  
Cc:  vdelecroix  Merged in:  
Authors:  Jana Lepšová, Sébastien Labbé  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/slabbe/31378 (Commits, GitHub, GitLab)  Commit:  f1b12db653679c5df041b8a323956d40b0b30786 
Dependencies:  Stopgaps: 
Description (last modified by )
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'
Change History (21)
comment:1 followup: ↓ 3 Changed 3 months ago by
comment:2 Changed 3 months ago by
 Description modified (diff)
comment:3 in reply to: ↑ 1 Changed 3 months ago by
comment:4 Changed 3 months ago by
 Branch changed from u/jlepsova/morphic to u/slabbe/31378
 Commit changed from 7876b866498c94b37e6ca80d559cb316d6bba038 to 86990a01f349123583801559982319e49d33e427
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 nth position of a fixed point

86990a0  linking morphic.py file to the sage words library

comment:5 Changed 3 months ago by
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 warnlong 72.7 randomseed=0 src/sage/combinat/words/morphic.py # 8 doctests failed 
comment:6 Changed 3 months ago by
 Branch changed from u/slabbe/31378 to u/jlepsova/morphic
 Commit changed from 86990a01f349123583801559982319e49d33e427 to d4e7081fdec60ff5d7145cfbe91d5b7be791c71c
comment:7 Changed 3 months ago by
 Commit changed from d4e7081fdec60ff5d7145cfbe91d5b7be791c71c to b8690fc4086307950f982b67b9665bbe06024347
Branch pushed to git repo; I updated commit sha1. New commits:
b8690fc  fixing some of the errors in word.py

comment:8 Changed 7 weeks ago by
 Milestone changed from sage9.3 to sage9.4
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.
comment:9 Changed 6 weeks ago by
 Branch changed from u/jlepsova/morphic to u/slabbe/31378
 Commit changed from b8690fc4086307950f982b67b9665bbe06024347 to 9573c34415eb2869423c9e91774df37b1780119f
comment:10 Changed 6 weeks ago by
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?
comment:11 Changed 6 weeks ago by
comment:12 Changed 4 weeks ago by
 Branch changed from u/slabbe/31378 to u/jlepsova/morphic
 Commit changed from 9573c34415eb2869423c9e91774df37b1780119f to ec5d4a7cfb7dc5e1d41cd46c611c5661ced3caa5
comment:13 Changed 4 weeks ago by
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) <ipythoninput22d1d9bdb9b26> in <module> > 1 s[Integer(2)] IndexError: string index out of range
comment:14 Changed 4 weeks ago by
 Status changed from new to needs_review
comment:15 Changed 4 weeks ago by
 Status changed from needs_review to needs_work
comment:16 Changed 8 days ago by
 Commit changed from ec5d4a7cfb7dc5e1d41cd46c611c5661ced3caa5 to 51d4db0b863b66f460eb8bf7ca17d79e50300a2e
Branch pushed to git repo; I updated commit sha1. New commits:
51d4db0  31378: fix comment 13

comment:17 Changed 8 days ago by
 Status changed from needs_work to needs_review
I solved comment 13 with regard to morphic.py but the issue with infinite_datatype remains.
comment:18 Changed 8 days ago by
 Branch changed from u/jlepsova/morphic to u/slabbe/31378
 Commit changed from 51d4db0b863b66f460eb8bf7ca17d79e50300a2e to 33eb4c15e936cb9e05604480a41dc574bb921d53
I fixed the remaining issue. Should be okay now.
I added a reference. I need to learn the new way of adding reference to sage...
New commits:
77a7759  adding more efficient way of stating a letter at an nth position of a fixed point

1916606  linking morphic.py file to the sage words library

2ad57b7  31378: incomplete changes

bd43972  fixed doctests in morphic.py

81d0ed8  fixing some of the errors in word.py

c6dc152  31378: fixing doctests in word.py

3602aa6  trying to repair the finite fixed point problem, something changed in word_infinite_datatypes.py, however

97515fd  31378: fix comment 13

33eb4c1  31378: fixed remaining issue, added doctests

comment:19 Changed 8 days ago by
 Commit changed from 33eb4c15e936cb9e05604480a41dc574bb921d53 to f1b12db653679c5df041b8a323956d40b0b30786
Branch pushed to git repo; I updated commit sha1. New commits:
f1b12db  31378: adding reference in the good place

comment:20 Changed 8 days ago by
Fixed the reference.
Needs review!
comment:21 Changed 4 days ago by
 Cc vdelecroix added
duplicate of #31370 ?