Opened 4 years ago

Closed 4 years ago

# Critical exponent for words

Reported by: Owned by: evandomme major sage-8.3 combinatorics MathExp2018, thursdaysbdx vdelecroix, slabbe Vincent Delecroix, Élise Vandomme Sébastien Labbé N/A 8a3717c 8a3717ca6bf49989b9da1a2656487b3cf6c3b723

We improve the algorithm computing the critical exponent for words.

For instance, consider the critical exponent of the length-1000 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

### comment:1 Changed 4 years ago by evandomme

• Branch set to u/evandomme/critical_exponent_for_words

### comment:2 Changed 4 years ago by evandomme

• Commit set to 7a3c1214c0dfdf9d21db02c3e978c28abfc920e8
• Status changed from new to needs_review

New commits:

 ​7a3c121 Better critical exponent

### comment:3 Changed 4 years ago by evandomme

• Type changed from PLEASE CHANGE to enhancement

### comment:4 Changed 4 years ago by evandomme

• Description modified (diff)

### comment:5 Changed 4 years ago by vdelecroix

Impressive timings! Cool :-)

### comment:6 Changed 4 years ago by vdelecroix

This following line can be removed

m = 0

(since m is later initialized with m = pft[l-j+k-2] 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 4 years ago by git

• 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 4 years ago by vdelecroix

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
Last edited 4 years ago by vdelecroix (previous) (diff)

### comment:9 Changed 4 years ago by vdelecroix

• Status changed from needs_review to needs_work

### comment:10 follow-up: ↓ 11 Changed 4 years ago by slabbe

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 4 years ago by vdelecroix

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).

Last edited 4 years ago by vdelecroix (previous) (diff)

### comment:12 Changed 4 years ago by vdelecroix

• 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

rebased on beta6

New commits:

 ​5cf1cc5 Better critical exponent ​adc11eb Modification according to comment 6 (raise an error for the empty word) ​8a3717c Fix error message

### comment:13 Changed 4 years ago by slabbe

• Reviewers set to Sébastien Labbé
• Status changed from needs_review to positive_review

Merci Sébastien!

### comment:15 Changed 4 years ago by vbraun

• Branch changed from u/vdelecroix/25525 to 8a3717ca6bf49989b9da1a2656487b3cf6c3b723
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.