[with patch, positive review] speed up is_lyndon method for words

[saliola]

The current implementation of the method is_lyndon is too slow

sage: c = words.ChristoffelWord(380447,34369)
sage: c
Lower Christoffel word of slope 380447/34369 over Ordered Alphabet [0, 1]
sage: c.length()
414816
sage: time c.is_lyndon()
CPU times: user 84.15 s, sys: 0.17 s, total: 84.33 s
Wall time: 84.52 s
True

[saliola]

DO NOT APPLY!

[saliola]

Don't apply trac_6631-is_lyndon.2.patch, it is a copy of the other, and should be deleted.

[saliola]

Here is the new timing:

sage: c = words.ChristoffelWord(380447,34369)
sage: time c.is_lyndon()
CPU times: user 1.15 s, sys: 0.00 s, total: 1.15 s
Wall time: 1.15 s
True

That's much better.

[vdelecroix]

The end of the loop can be simplified (there is no break statement in the loop, and we know that j==n at the end).

while j < n:
    [...]
else:
    return j - i == n

could become:

while j < n:
    [...]
return i == 0

[saliola]

depends on #6627;

[saliola]

Replying to vdelecroix:

The end of the loop can be simplified (there is no break statement in the loop, and we know that j==n at the end).

while j < n:
    [...]
else:
    return j - i == n

could become:

while j < n:
    [...]
return i == 0

Done in the new patch. (If you give this new patch a positive review, then change 'needs review' to 'positive review'.)

[mvngu]

reviewer patch: fixes typo

[mvngu]

The patch trac_6631-reviewer.patch fixes a typo introduced by trac_6631-is_lyndon.patch.

[mvngu]

Merged:

1. trac_6631-is_lyndon.patch
2. trac_6631-reviewer.patch