Opened 2 years ago
Closed 2 years ago
#25525 closed enhancement (fixed)
Critical exponent for words
Reported by:  evandomme  Owned by:  

Priority:  major  Milestone:  sage8.3 
Component:  combinatorics  Keywords:  MathExp2018, thursdaysbdx 
Cc:  vdelecroix, slabbe  Merged in:  
Authors:  Vincent Delecroix, Élise Vandomme  Reviewers:  Sébastien Labbé 
Report Upstream:  N/A  Work issues:  
Branch:  8a3717c (Commits)  Commit:  8a3717ca6bf49989b9da1a2656487b3cf6c3b723 
Dependencies:  Stopgaps: 
Description (last modified by )
We improve the algorithm computing the critical exponent for words.
For instance, consider the critical exponent of the length1000 prefix of the Fibonacci word,
fibo = words.FibonacciWord()[:1000] % time fibo.critical_exponent()
Before it took:
CPU times: user 1min 19s, sys: 398 ms, total: 1min 19s
Wall time: 1min 20s
173/48
Now, it takes:
CPU times: user 1.3 s, sys: 64.1 ms, total: 1.36 s
Wall time: 1.34 s.
173/48
Change History (15)
comment:1 Changed 2 years ago by
 Branch set to u/evandomme/critical_exponent_for_words
comment:2 Changed 2 years ago by
 Commit set to 7a3c1214c0dfdf9d21db02c3e978c28abfc920e8
 Status changed from new to needs_review
comment:3 Changed 2 years ago by
 Type changed from PLEASE CHANGE to enhancement
comment:4 Changed 2 years ago by
 Description modified (diff)
comment:5 Changed 2 years ago by
Impressive timings! Cool :)
comment:6 Changed 2 years ago by
This following line can be removed
m = 0
(since m
is later initialized with m = pft[lj+k2]
before it is used)
It would be nice to add a little bit of comment in the code
pft = [0] * wlen # the prefix function table queue = [(0, 0, 1, 0)] # suffix tree vertices to visit for DFS best_exp = 1 # best exponent so far
You can replace w
with self
instead of having two variables pointing to the same object.
What should be the critical exponent of the empty word? (I guess the function currently returns 1
but should rather raise an error). There should be a doctest for this.
comment:7 Changed 2 years ago by
 Commit changed from 7a3c1214c0dfdf9d21db02c3e978c28abfc920e8 to da0b349a94de17b3e96cf4c7cb3f41cbf48dd769
Branch pushed to git repo; I updated commit sha1. New commits:
da0b349  Modification according to comment 6 (raise an error for the empty word)

comment:8 Changed 2 years ago by
The syntax
raise ValueError, 'The empty word has no critical exponent.'
is valid in Python2 but not Python3. To prepare the future, use
raise ValueError('The empty word has no critical exponent.')
(which is Python2 and Python3 valid).
And convention for the error messages: keep it short, start with a lower case and no punctuation. Similar to
sage: l = [] sage: l[1] sage: l = [] sage: l[1] Traceback (most recent call last): ... IndexError: list index out of range
comment:9 Changed 2 years ago by
 Status changed from needs_review to needs_work
comment:10 followup: ↓ 11 Changed 2 years ago by
Is it possible to add a reference in the documentation of the method to the article where this algorithm is defined?
I have time this morning to review the code. Otherwise, I will review it next Thursday.
comment:11 in reply to: ↑ 10 Changed 2 years ago by
Replying to slabbe:
Is it possible to add a reference in the documentation of the method to the article where this algorithm is defined?
The algorithm is the same as before. It is just more efficiently done. You just go through all factors of the word and compute the exponent. The version in this branch is better because
 instead of running through the factors it performs a depth first search in the suffix tree
 it does not build the factors, it simply updates the prefix function table
I have time this morning to review the code. Otherwise, I will review it next Thursday.
comment:8 should be addressed before review (status is needs_work).
comment:12 Changed 2 years ago by
 Branch changed from u/evandomme/critical_exponent_for_words to u/vdelecroix/25525
 Commit changed from da0b349a94de17b3e96cf4c7cb3f41cbf48dd769 to 8a3717ca6bf49989b9da1a2656487b3cf6c3b723
 Status changed from needs_work to needs_review
comment:13 Changed 2 years ago by
 Reviewers set to Sébastien Labbé
 Status changed from needs_review to positive_review
comment:14 Changed 2 years ago by
Merci Sébastien!
comment:15 Changed 2 years ago by
 Branch changed from u/vdelecroix/25525 to 8a3717ca6bf49989b9da1a2656487b3cf6c3b723
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Better critical exponent