error in the computing of the approximate order in LazyPowerSeries

[MatthieuDien]

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 = x³ 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

CC: @mantepse

Component: combinatorics

Keywords: LazyPowerSeries aorder approximate order

Reviewer: Travis Scrimshaw, Martin Rubey

Issue created by migration from https://trac.sagemath.org/ticket/14685

[MatthieuDien]

Description changed:

--- 
+++ 
@@ -50,3 +50,7 @@
      
          if hasattr(self, '_reference') and self._reference is not None:
 ```
+
+I commited it with the number 18037 on the mercurial server
+
+It's my first patch, sorry if i did a mistake.

[fchapoton]

comment:2

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.

[MatthieuDien]

Description changed:

--- 
+++ 
@@ -14,43 +14,70 @@
 sage: B.aorder
 1
 ```
+The good result should be 3 and not 1 (the order of the series B = x^3 is 3 not 1 )
 
-Here, a patch :
+Here, a patch which fix that:
 
 ```
-diff --git a/sage/combinat/species/series.py b/sage/combinat/species/series.py
---- a/sage/combinat/species/series.py
-+++ b/sage/combinat/species/series.py
-@@ -631,6 +631,7 @@
-                         self.aorder += 1
-                         ao += 1
-                     else:
-+                        self.order = ao
-                         break
+--- series_old.py	2013-06-08 13:48:40.490566975 +0200
++++ series.py	2013-06-08 14:00:41.903399503 +0200
+@@ -624,17 +624,17 @@
+             c = self._stream
+             n = c.number_computed()
+ 
++            while ao < n:
++                if self._stream[ao] == 0:
++                    self.aorder += 1
++                    ao += 1
++                else:
++                    self.order = ao
++                    break
+ 
+-            if ao == 0 and n > 0:
+-                while ao < n:
+-                    if self._stream[ao] == 0:
+-                        self.aorder += 1
+-                        ao += 1
+-                    else:
+-                        break
  
              #Try to recognize the zero series
-@@ -643,8 +644,17 @@
+-            if ao == n:
++            if ao == n and n > 0:
+                 #For non-constant series, we cannot do anything
+                 if not c.is_constant():
+                     return
+@@ -642,11 +642,7 @@
+                     self.aorder = inf
                      self.order  = inf
                      return
-                 
+-                
 -            if ao < n:
 -                self.order = ao
-+            if self.order == unk:
-+                while ao < n:
-+                    if self._stream[ao] == 0:
-+                        self.aorder += 1
-+                        ao += 1
-+                    else:
-+                        self.order = ao
-+                        break
+-            
+-    
 +
-+            # if ao < n:
-+            #     self.order = ao
-             
-     
          if hasattr(self, '_reference') and self._reference is not None:
+             self._reference._copy(self)
+```
+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
 ```
 
-I commited it with the number 18037 on the mercurial server
+What we expected.
 
-It's my first patch, sorry if i did a mistake.
+
+PS : Thanks you for the commment, I tried to answer.
+
+

[MatthieuDien]

Description changed:

--- 
+++ 
@@ -1,8 +1,6 @@
 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 :
+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)
@@ -14,7 +12,7 @@
 sage: B.aorder
 1
 ```
-The good result should be 3 and not 1 (the order of the series B = x^3 is 3 not 1 )
+The good result should be 3 and not 1 (the order of the series B = x<sup>3</sup> is 3 not 1 )
 
 Here, a patch which fix that:
 
@@ -62,7 +60,7 @@
 ```
 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 : 
+After the patch, we obtain :
 
 ```
 sage: R = LazyPowerSeriesRing(QQ)
@@ -74,10 +72,6 @@
 sage: B.aorder
 3
 ```
-
 What we expected.
 
-
 PS : Thanks you for the commment, I tried to answer.
-
-

[MatthieuDien]

Description changed:

--- 
+++ 
@@ -74,4 +74,4 @@
 ```
 What we expected.
 
-PS : Thanks you for the commment, I tried to answer.
+PS : Thanks you for the commment, I tried to answer it.

[fchapoton]

comment:6

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

[nthiery]

comment:7

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

[MatthieuDien]

comment:8

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

[MatthieuDien]

Description changed:

--- 
+++ 
@@ -14,50 +14,6 @@
 ```
 The good result should be 3 and not 1 (the order of the series B = x<sup>3</sup> is 3 not 1 )
 
-Here, a patch which fix that:
-
-```
---- series_old.py	2013-06-08 13:48:40.490566975 +0200
-+++ series.py	2013-06-08 14:00:41.903399503 +0200
-@@ -624,17 +624,17 @@
-             c = self._stream
-             n = c.number_computed()
- 
-+            while ao < n:
-+                if self._stream[ao] == 0:
-+                    self.aorder += 1
-+                    ao += 1
-+                else:
-+                    self.order = ao
-+                    break
- 
--            if ao == 0 and n > 0:
--                while ao < n:
--                    if self._stream[ao] == 0:
--                        self.aorder += 1
--                        ao += 1
--                    else:
--                        break
- 
-             #Try to recognize the zero series
--            if ao == n:
-+            if ao == n and n > 0:
-                 #For non-constant series, we cannot do anything
-                 if not c.is_constant():
-                     return
-@@ -642,11 +642,7 @@
-                     self.aorder = inf
-                     self.order  = inf
-                     return
--                
--            if ao < n:
--                self.order = ao
--            
--    
-+
-         if hasattr(self, '_reference') and self._reference is not None:
-             self._reference._copy(self)
-```
 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 :
@@ -74,4 +30,5 @@
 ```
 What we expected.
 
-PS : Thanks you for the commment, I tried to answer it.
+PS : Thanks you for the commments, I tried to answer them.
+PS 2 : I modified the patch as you asked

[mwhansen]

comment:10

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.