[Sage] #8490: Bad behavior of is_square

Sage

unread,

Mar 10, 2010, 11:38:46 AM3/10/10

to sage...@googlegroups.com

#8490: Bad behavior of is_square_free for Words
-----------------------------+----------------------------------------------
Reporter: vdelecroix | Owner: vdelecroix
Type: defect | Status: new
Priority: major | Milestone: sage-4.3.4
Component: combinatorics | Keywords: word
Author: vdelecroix | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
The method is_square_free of sage.combinat.words.word.Word returns the
wrong value in special case (including squares !)

{{{
sage: Word("aa").is_square_free() # the most funny
True
sage: Word("baa").is_square_free()
True
sage: Word("cbaa").is_square_free()
True
sage: Word("dcbaa").is_square_free()
True
}}}

--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8490>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica, and MATLAB

Sage

unread,

Mar 10, 2010, 11:46:58 AM3/10/10

to sage...@googlegroups.com

#8490: Bad behavior of is_square_free for Words
-----------------------------+----------------------------------------------
Reporter: vdelecroix | Owner: vdelecroix

Type: defect | Status: needs_review

Changes (by vdelecroix):

* status: new => needs_review

--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8490#comment:1>

Sage

unread,

Mar 10, 2010, 12:00:45 PM3/10/10

to sage...@googlegroups.com

#8490: Bad behavior of is_square_free for Words
-----------------------------+----------------------------------------------
Reporter: vdelecroix | Owner: vdelecroix

Type: defect | Status: needs_review

Description changed by vdelecroix:

Old description:

> The method is_square_free of sage.combinat.words.word.Word returns the
> wrong value in special case (including squares !)
>
> {{{
> sage: Word("aa").is_square_free() # the most funny
> True
> sage: Word("baa").is_square_free()
> True
> sage: Word("cbaa").is_square_free()
> True
> sage: Word("dcbaa").is_square_free()
> True
> }}}

New description:

The method is_square_free of sage.combinat.words.word.Word returns the

wrong value in special cases (including squares !)

{{{
sage: Word("aa").is_square_free() # the funniest

True
sage: Word("baa").is_square_free()
True
sage: Word("cbaa").is_square_free()
True
sage: Word("dcbaa").is_square_free()
True
}}}

--

--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8490#comment:2>

Sage

unread,

Mar 10, 2010, 12:16:25 PM3/10/10

to sage...@googlegroups.com

#8490: Bad behavior of is_square_free for Words

---------------------------------+------------------------------------------
Reporter: vdelecroix | Owner: vdelecroix
Type: defect | Status: positive_review

Priority: major | Milestone: sage-4.3.4
Component: combinatorics | Keywords: word

Author: Vincent Delecroix | Upstream: N/A
Reviewer: Mike Hansen | Merged:
Work_issues: |
---------------------------------+------------------------------------------
Changes (by newvalueoldvalue):

* status: needs_review => positive_review
* reviewer: => Mike Hansen
* author: vdelecroix => Vincent Delecroix

Comment:

Looks good to me.

--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8490#comment:3>

Sage

unread,

Mar 10, 2010, 12:24:34 PM3/10/10

to sage...@googlegroups.com

#8490: Bad behavior of is_square_free for Words

---------------------------------+------------------------------------------
Reporter: vdelecroix | Owner: vdelecroix
Type: defect | Status: needs_work

Priority: major | Milestone: sage-4.3.4
Component: combinatorics | Keywords: word

Author: Vincent Delecroix | Upstream: N/A
Reviewer: Mike Hansen | Merged:
Work_issues: |
---------------------------------+------------------------------------------

Changes (by vdelecroix):

* status: positive_review => needs_work

Comment:

Oups, intersection with #8429 which refactors the code of
sage.combinat.words.

I post soon a new patch that apply only after #8429 and I think it's
better.

--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8490#comment:4>

Sage

unread,

Apr 28, 2010, 6:12:41 AM4/28/10

to sage...@googlegroups.com

#8490: Bad behavior of is_square_free for Words

---------------------------------+------------------------------------------
Reporter: vdelecroix | Owner: vdelecroix
Type: defect | Status: needs_work
Priority: major | Milestone: sage-4.4.1
Component: combinatorics | Keywords: word

Author: Vincent Delecroix | Upstream: N/A
Reviewer: Mike Hansen | Merged:
Work_issues: |
---------------------------------+------------------------------------------

Comment(by slabbe):

The same bug was occuring with {{{is_cube_free}}} :

{{{
sage: Word('111').is_cube_free()
True
sage: Word('2111').is_cube_free()
True
sage: Word('32111').is_cube_free()
True
}}}

I just applied a patch which fixes this problem. I changed some doctests
of both {{{is_square_free}}} and {{{is_cube_free}}}. I also removed a
useless slice in the code of both functions and this gives good
improvements in timings :

BEFORE:

{{{
sage: t = words.ThueMorseWord()
sage: %timeit t[:100].is_cube_free()
5 loops, best of 3: 3.13 s per loop
}}}

AFTER:

{{{
sage: t = words.ThueMorseWord()
sage: %timeit t[:100].is_cube_free()
5 loops, best of 3: 1.18 s per loop
}}}

--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8490#comment:5>

Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica, and MATLAB

--
You received this message because you are subscribed to the Google Groups "sage-combinat-commits" group.
To post to this group, send email to sage-combi...@googlegroups.com.
To unsubscribe from this group, send email to sage-combinat-co...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/sage-combinat-commits?hl=en.

Sage

unread,

Apr 28, 2010, 6:21:34 AM4/28/10

to sage...@googlegroups.com

#8490: Bad behavior of is_square_free for Words

--------------------------------------------------+-------------------------
Reporter: vdelecroix | Owner: vdelecroix
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.4.1
Component: combinatorics | Keywords: word
Author: Vincent Delecroix, Sébastien Labbé | Upstream: N/A

Reviewer: Mike Hansen | Merged:
Work_issues: |

--------------------------------------------------+-------------------------
Changes (by newvalueoldvalue):

* status: needs_work => needs_review
* author: Vincent Delecroix => Vincent Delecroix, Sébastien Labbé

--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8490#comment:6>

Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica, and MATLAB

Sage

unread,

May 9, 2010, 1:09:18 PM5/9/10

to sage...@googlegroups.com

#8490: Bad behavior of is_square_free for Words

--------------------------------------------------+-------------------------
Reporter: vdelecroix | Owner: vdelecroix
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.4.2
Component: combinatorics | Keywords: word

Author: Vincent Delecroix, Sébastien Labbé | Upstream: N/A
Reviewer: Mike Hansen | Merged:
Work_issues: |
--------------------------------------------------+-------------------------

Comment(by ncohen):

Hello !! This patch is finem except for a small unimportant thing which
bothered me :

{{{
for end in xrange(start+3, L+1, 3):
}}}

Why go up to L+1 when the last letter is L-1 ? The algorithm is still
correct as

{{{
Word("abc")[:50000]
}}}

raises no exception, but as there is no reason to.... So I give a positive
review to the patches above, and trac_8490_review-ncohen.patch is left to
be reviewed by anyone other than me (quoting Minh) :-)

Thank you for this patch !!

Nathann

--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8490#comment:7>

Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica, and MATLAB

Sage

unread,

May 9, 2010, 1:10:26 PM5/9/10

to sage...@googlegroups.com

#8490: Bad behavior of is_square_free for Words

--------------------------------------------------+-------------------------
Reporter: vdelecroix | Owner: vdelecroix

Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.4.2

Component: combinatorics | Keywords: word

Author: Vincent Delecroix, Sébastien Labbé | Upstream: N/A
Reviewer: Mike Hansen | Merged:
Work_issues: |
--------------------------------------------------+-------------------------

Comment(by ncohen):

The patches are to be applied in this order :

* trac_8490-square_free-vd.patch
* trac_8490_review-sl.patch
* trac_8490_review-ncohen.patch

Nathann

--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8490#comment:8>

Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica, and MATLAB

Sage

unread,

May 13, 2010, 10:03:24 AM5/13/10

to sage...@googlegroups.com

#8490: Bad behavior of is_square_free for Words

--------------------------------------------------+-------------------------
Reporter: vdelecroix | Owner: vdelecroix

Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.4.2

Component: combinatorics | Keywords: word

Author: Vincent Delecroix, Sébastien Labbé | Upstream: N/A
Reviewer: Mike Hansen | Merged:
Work_issues: |
--------------------------------------------------+-------------------------

Comment(by slabbe):

Replying to [comment:7 ncohen]:

> Hello !! This patch is finem except for a small unimportant thing which
bothered me :
>
> {{{
> for end in xrange(start+3, L+1, 3):
> }}}
>
> Why go up to L+1 when the last letter is L-1 ?

First, xrange returns a left-closed and right-open interval. Hence, one
needs to write something like `xrange(0,L+1)` if one wants to go up to `L`
:

{{{
sage: list(xrange(0,5))
[0, 1, 2, 3, 4]
}}}

Second, the variable `end` is not used to get a specific item in self but
for slicing self. Hence, if one wants to consider all the slicing
possibilities, the variable `end` must take the last possible value `L`:

{{{
sage: list(xrange(0,5)) [2:5] #is good
[2, 3, 4]
sage: list(xrange(0,5)) [2:4] #forgets the last letter
[2, 3]
}}}

Hence, your patch is strange in the sense that doctests should not pass!

> The algorithm is still correct as
>
> {{{
> Word("abc")[:50000]
> }}}
>
> raises no exception, but as there is no reason to....

We made the choice of following the Python behavior for slices that goes
too far:

{{{
sage: L = range(10)
sage: L
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: L[:100]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
}}}

Sébastien

--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8490#comment:9>

Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica, and MATLAB

Sage

unread,

May 13, 2010, 10:09:56 AM5/13/10

to sage...@googlegroups.com

#8490: Bad behavior of is_square_free for Words

--------------------------------------------------+-------------------------
Reporter: vdelecroix | Owner: vdelecroix

Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.4.2

Component: combinatorics | Keywords: word

Author: Vincent Delecroix, Sébastien Labbé | Upstream: N/A
Reviewer: Mike Hansen | Merged:
Work_issues: |
--------------------------------------------------+-------------------------

Comment(by slabbe):

Replying to [comment:8 ncohen]:

> The patches are to be applied in this order :
>
> * trac_8490-square_free-vd.patch
> * trac_8490_review-sl.patch
> * trac_8490_review-ncohen.patch
>
> Nathann

The patch `trac_8490_review-ncohen.patch` reintroduce the same bug as the
current ticket is trying to solve. Hence, I think the patches are to be
reviewed in this order again :

* trac_8490-square_free-vd.patch
* trac_8490_review-sl.patch

Sébastien

--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8490#comment:10>

Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica, and MATLAB

Sage

unread,

May 13, 2010, 10:52:05 AM5/13/10

to sage...@googlegroups.com

#8490: Bad behavior of is_square_free for Words

--------------------------------------------------+-------------------------
Reporter: vdelecroix | Owner: vdelecroix

Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.4.2

Component: combinatorics | Keywords: word

Author: Vincent Delecroix, Sébastien Labbé | Upstream: N/A
Reviewer: Mike Hansen | Merged:
Work_issues: |
--------------------------------------------------+-------------------------

Comment(by ncohen):

Perfectly right !! sorryyyyyyyyyyy !!! :-)

Nathann

--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8490#comment:11>

Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica, and MATLAB

Sage

unread,

May 16, 2010, 1:01:10 PM5/16/10

to sage...@googlegroups.com

#8490: Bad behavior of is_square_free for Words

--------------------------------------------------+-------------------------
Reporter: vdelecroix | Owner: vdelecroix
Type: defect | Status: positive_review
Priority: major | Milestone: sage-4.4.2
Component: combinatorics | Keywords: word

Author: Vincent Delecroix, Sébastien Labbé | Upstream: N/A
Reviewer: Mike Hansen | Merged:
Work_issues: |
--------------------------------------------------+-------------------------

Changes (by ncohen):

* status: needs_review => positive_review

Comment:

Well, then short of this, which was my mistake, I noticed nothing wrong
with these two patches ! :-)

Nathann

--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8490#comment:12>

Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica, and MATLAB

Sage

unread,

Jun 5, 2010, 6:30:25 PM6/5/10

to sage...@googlegroups.com

#8490: Bad behavior of is_square_free for Words

-------------------------------+--------------------------------------------
Reporter: vdelecroix | Owner: vdelecroix
Type: defect | Status: closed
Priority: major | Milestone: sage-4.4.4
Component: combinatorics | Resolution: fixed

Keywords: word | Author: Vincent Delecroix, Sébastien Labbé

Upstream: N/A | Reviewer: Mike Hansen, Nathann Cohen
Merged: sage-4.4.4.alpha0 | Work_issues:
-------------------------------+--------------------------------------------
Changes (by mhansen):

* status: positive_review => closed
* reviewer: Mike Hansen => Mike Hansen, Nathann Cohen
* resolution: => fixed
* merged: => sage-4.4.4.alpha0

--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8490#comment:13>

Reply all

Reply to author

Forward

[Sage] #8490: Bad behavior of is_square_free for Words

Sage

Sage

Sage

Sage

Sage

Sage

Sage

Sage

Sage

Sage

Sage

Sage

Sage

Sage