Opened 9 years ago

Last modified 14 months ago

#14685 needs_review defect

error in the computing of the approximate order in LazyPowerSeries

Reported by: Matthieu Dien Owned by: Sage Combinat CC user
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: combinatorics Keywords: LazyPowerSeries aorder approximate order
Cc: Martin Rubey Merged in:
Authors: Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Matthieu Dien)

Hi,

I found a bug in the LazyPowerSeries? class of package combinat. There is mistake in the computing of the approximate order of a serie. A demonstration of the bug :

sage: R = LazyPowerSeriesRing(QQ)
sage: B = R([0,0,0,1,0])
sage: B.aorder
0
sage: B.coefficients(10)
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
sage: B.aorder
1

The good result should be 3 and not 1 (the order of the series B = x3 is 3 not 1 )

The bug is that the aorder is computed one time and never updated. This is because the order was assigned the first time then the condition self.order != unk becomes false and the update never comes.

After the patch, we obtain :

sage: R = LazyPowerSeriesRing(QQ)
sage: B = R([0,0,0,1,0])
sage: B.aorder
0
sage: B.coefficients(10)
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
sage: B.aorder
3

What we expected.

PS : Thanks you for the commments, I tried to answer them. PS 2 : I modified the patch as you asked

Attachments (2)

trac_14685_bug_aorder_lazypowerseries.patch (2.5 KB) - added by Mike Hansen 9 years ago.
trac_14685-darijs_mod.patch (1.9 KB) - added by Darij Grinberg 9 years ago.
Alternative version of the patch, which applies on my system

Download all attachments as: .zip

Change History (30)

comment:1 Changed 9 years ago by Matthieu Dien

Description: modified (diff)
Type: PLEASE CHANGEdefect

comment:2 Changed 9 years ago by Frédéric Chapoton

Bienvenue à bord !

Your patch does not looks good: it contains three times the same thing. It is necessary to make it again in a more clean way.

It is not clear to me what the expected result should be in the example given above. Which answer is correct and which one is not ?

Apart from that, it would be good to add a test to check that the error is corrected. Something like

One checks that :trac:`14685` is solved::

    sage: R = LazyPowerSeriesRing(QQ)

and then the appropriate example.

comment:3 Changed 9 years ago by Matthieu Dien

Description: modified (diff)

comment:4 Changed 9 years ago by Matthieu Dien

Description: modified (diff)

comment:5 Changed 9 years ago by Matthieu Dien

Description: modified (diff)

comment:6 Changed 9 years ago by Frédéric Chapoton

Hello,

the corrected behaviour should be added to the code, in the documentation at the start of the function.

Your patch still looks strange. How do you make it ?

You should

1) cd to the directory sage-5.9/devel/sage-main/
2) create a patch with hg qnew trac_xxxxx_name_of_the_patch.patch
3) edit the sources
4) put the changes into the patch by hg qrefresh (then either go to step 3 or step 5)
5) edit the header of the patch by hg qrefresh -e
6) export the patch by hg export tip > filename (for example $HOME/trac_xxxxx_name_of_the_patch.patch)
7) put this exported file in trac
Last edited 9 years ago by Frédéric Chapoton (previous) (diff)

comment:7 Changed 9 years ago by Nicolas M. Thiéry

Hi!

Thanks for working on the lazy power series code; it needs some love.

Just one thing to be careful with; I haven't looked in detail in your code, so maybe it takes care of this already:

The method might be passed as argument a lazy power series implemented by a function f(n) which returns always 0; or some non zero coefficient but only for n very large. In such a case we don't want to run forever: this is about computing an approximation of the order, and often, knowing that the order is at least 1 or at least 2 is sufficient for the purpose (initializing the recurrence for computing series defined recursively).

Of course, there are case where we do want the exact order, even at the price of running for a long time.

Its possible that the interface needs a bit of cleaning up so that the distinction between approximate order and order would be well exposed (and by the way maybe this should really be called valuation rather than order).

comment:8 Changed 9 years ago by Matthieu Dien

for chapoton :

I made the patch with a diff -Naur but I will fix this. Thank you for the detailed method.

for nthiery :

I am not sure to understand what you said : currently the computing of the approximate order cost is amortized on every request for a serie's term (and it's a little cost). Normally, the order should be known when the approximate order reaches him.

The patch keeps this behavior. This was your question ?

Moreover, the current version do not compute the right order too :

sage: R = LazyPowerSeriesRing(QQ)
sage: B = R([0,0,0,1,0])
sage: B.order
Unknown series order
sage: B.coefficients(10)
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
sage: B.aorder
0   #instead of 3

comment:9 Changed 9 years ago by Matthieu Dien

Description: modified (diff)

comment:10 Changed 9 years ago by Mike Hansen

Authors: Matthieu Dien
Reviewers: Mike Hansen
Status: newneeds_review

I posted a version of the patch which fixes the commit message. This looks good to me, and I agree with Matthieu's assessment of the amortized costs.

comment:11 Changed 9 years ago by Mike Hansen

Status: needs_reviewpositive_review

comment:12 in reply to:  11 Changed 9 years ago by Matthieu Dien

Replying to mhansen: Thank you !

Changed 9 years ago by Mike Hansen

comment:13 Changed 9 years ago by Mike Hansen

The new patch should apply.

comment:14 Changed 9 years ago by Mike Hansen

Apply trac_14685_bug_aorder_lazypowerseries.patch​

comment:15 Changed 9 years ago by Darij Grinberg

What's going wrong?

darij@travis-virtualbox:~/sage-5.11.beta3/devel/sage-main/sage/combinat$ hg qpush
applying trac_14685_bug_aorder_lazypowerseries.patch
patching file sage/combinat/species/series.py
Hunk #2 FAILED at 641
Hunk #3 FAILED at 660
2 out of 3 hunks FAILED -- saving rejects to file sage/combinat/species/series.py.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac_14685_bug_aorder_lazypowerseries.patch
darij@travis-virtualbox:~/sage-5.11.beta3/devel/sage-main/sage/combinat$ 

Series file:

trac_14808-recoils_of_permutations-ts.patch
trac_14117-jordan_normal_form-dg-v3.patch
trac_7983-major_index_and_other_tableau_fixes-dg.patch
trac_14748_deprecationwarning.patch
trac_14136-p_partition_enumerator_folded.patch
trac_14507-tropical_semiring-ts.patch
trac_14775-symmetric_functions_extended-dg.patch
trac_14783-toggles_on_order_ideals-jsdg.patch
trac_14516-crystals_speedup-ts.2.patch
trac_14519-cynthonize_element_wrapper-ts.patch
trac_8386_really_just_moving-fc.patch
trac_8386_big_clean_fc.patch
trac_8386_assert_removal.patch
trac_14772-remove_cc_permutations-ts.patch
trac_13589-categories-c3_under_control-nt.patch
trac_14884-tableau_times_id-dg.patch
trac_14883-remove_times_id-dg.patch
trac_14101-remove_cc_skew-ts.patch
trac_14882-backtrack_longtime-dg-v2.patch
trac_14881-symmetric_group_algebra_rebased-dg.patch
trac_13214_hom_finite_field.patch
trac_14860-bug-binary-trees-vp.patch
trac_12571-shifted_shuffle_of_permutations-reviewed.patch
trac_14685_bug_aorder_lazypowerseries.patch

comment:16 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11sage-5.12
Status: positive_reviewneeds_work

This doesn't apply to sage-5.11.beta3:

applying /release/merger/patches/trac_14685_bug_aorder_lazypowerseries.patch
patching file sage/combinat/species/series.py
Hunk #2 FAILED at 641
Hunk #3 FAILED at 660
2 out of 3 hunks FAILED -- saving rejects to file sage/combinat/species/series.py.rej
abort: patch failed to apply

Changed 9 years ago by Darij Grinberg

Attachment: trac_14685-darijs_mod.patch added

Alternative version of the patch, which applies on my system

comment:17 Changed 9 years ago by Darij Grinberg

I've attached a modified version of the patch that applies on my system. Since Jeroen, me and the patchbot seem to be stumbling over the same error, I assume this might be of some help. All I've changed were deleted lines, which gives me some hope I didn't break anything, so I'm going to be blunt:

Patchbot:

apply trac_14685-darijs_mod.patch​

comment:18 Changed 9 years ago by Darij Grinberg

Milestone: sage-5.12sage-5.11

comment:19 Changed 9 years ago by Darij Grinberg

Status: needs_workneeds_review

comment:20 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11sage-5.12

comment:21 Changed 9 years ago by Martin Rubey

Cc: Martin Rubey added

comment:22 Changed 9 years ago by Mike Hansen

A fix is in #15673

comment:23 Changed 9 years ago by For batch modifications

Milestone: sage-6.1sage-6.2

comment:24 Changed 8 years ago by For batch modifications

Milestone: sage-6.2sage-6.3

comment:25 Changed 8 years ago by For batch modifications

Milestone: sage-6.3sage-6.4

comment:26 Changed 8 years ago by Frédéric Chapoton

Milestone: sage-6.4sage-6.6
Status: needs_reviewneeds_work

Needs a working git branch

comment:27 Changed 6 years ago by Jakob Kroeker

Stopgaps: wrongAnswerMarker

comment:28 Changed 14 months ago by Travis Scrimshaw

Authors: Matthieu Dien
Milestone: sage-6.6sage-duplicate/invalid/wontfix
Reviewers: Mike HansenTravis Scrimshaw
Status: needs_workneeds_review
Stopgaps: wrongAnswerMarker

I propose closing this as invalid since this is only meant to be the approximate order, not the actual order. So as long as aorder <= order, then it is correct. (Although it might be considered a missed optimization.)

This is also set to be replaced soon; see #31651.

Note: See TracTickets for help on using tickets.