Opened 7 years ago
Closed 6 years ago
#15714 closed enhancement (fixed)
implement CFiniteSequence
Reported by:  rws  Owned by:  rws 

Priority:  major  Milestone:  sage6.8 
Component:  combinatorics  Keywords:  recurrence, sequence, ogf 
Cc:  burcin, mmezzarobba, VivianePons  Merged in:  
Authors:  Ralf Stephan, Viviane Pons  Reviewers:  Ralf Stephan, Viviane Pons 
Report Upstream:  N/A  Work issues:  
Branch:  84c909d (Commits, GitHub, GitLab)  Commit:  84c909de109ee7c78cfd07eb320c71d364b8e25a 
Dependencies:  Stopgaps: 
Description (last modified by )
The upcoming inclusion of ore_algebra will provide the means for a PFiniteSequence class. Nevertheless a lightweight implementation of CFiniteSequence has its place in Sage, and it is available now.
The interface:
 constructed from generating function or recurrence
 guessed from sequence
 provides gf, recurrence, sequence, so practically a conversion between all three
 other: textual description of recurrence, sequence iterator
Possible extensions, not implemented: output of egf, power sum closed form
Change History (56)
comment:1 Changed 7 years ago by
 Description modified (diff)
comment:2 Changed 7 years ago by
 Description modified (diff)
comment:3 Changed 7 years ago by
 Branch set to u/rws/ticket/15714
 Created changed from 01/23/14 10:56:52 to 01/23/14 10:56:52
 Modified changed from 01/23/14 10:59:24 to 01/23/14 10:59:24
comment:4 Changed 7 years ago by
 Commit set to 9d8a0eb2b073cb00a68218ff9a6246b880d500b7
comment:5 Changed 7 years ago by
 Cc burcin added
comment:6 Changed 7 years ago by
 Cc mmezzarobba added
comment:7 Changed 7 years ago by
 Commit changed from 9d8a0eb2b073cb00a68218ff9a6246b880d500b7 to 70a29e1f99da5f6bf4d3a465ab26a79b6c9575c2
Branch pushed to git repo; I updated commit sha1. New commits:
70a29e1  core functionality

comment:8 Changed 7 years ago by
 Commit changed from 70a29e1f99da5f6bf4d3a465ab26a79b6c9575c2 to 6df1fc6a4e7027facf3835574ba893b8af641d0e
Branch pushed to git repo; I updated commit sha1. New commits:
6df1fc6  guess(), random_element(), some refactoring

comment:9 Changed 7 years ago by
 Commit changed from 6df1fc6a4e7027facf3835574ba893b8af641d0e to 9095be01500c51a0a32b0ffe987dc94a32fd4b96
Branch pushed to git repo; I updated commit sha1. New commits:
9095be0  ref doc completed; coefficients(), slicing added

comment:10 Changed 7 years ago by
 Commit changed from 9095be01500c51a0a32b0ffe987dc94a32fd4b96 to f73e11e1396b68c1668c4808b25edcf38c23163f
Branch pushed to git repo; I updated commit sha1. New commits:
f73e11e  handle ogf > 1

comment:11 Changed 7 years ago by
 Description modified (diff)
 Keywords sequence added
 Status changed from new to needs_review
 Summary changed from generalize BinaryRecurrenceSequence to implement CFiniteSequence
comment:12 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:13 Changed 7 years ago by
 Status changed from needs_review to needs_work
Some more comments:
 Your code is apparently limited to sequences with integer or rational coefficients. IMHO it would be best to handle Cfinite sequences over arbitrary rings (or perhaps integral domains?). If you don't want to do that, the scope of the code should be clearly documented and there should be a few checks in suitable places^{[1]}.
 How about making CFiniteSequences Elements of a proper Parent? Sure, it is not absolutely essential at this point, but that's something we will certainly want in the long run—Cfinite sequences [over a given ring] form a ring!—, and designing a suitable interface from the start would save the trouble of deprecating the current one later on!
 If you do implement a "ring of CFinite sequences over ...", I'd suggest moving it outside of combinat (perhaps to a new package
sage.rings.sequences
?).
[1] Currently, the following examples all behave differently:
sage: R.<x> = RR[]; fibo = CFiniteSequence(x/(1xx^2)); fibo[10] 55 sage: R.<x> = GF(3)[]; fibo = CFiniteSequence(x/(1xx^2)); fibo[10] ... ValueError: Cannot convert to CFiniteSequence. sage: R.<x> = CC[]; fibo = CFiniteSequence(x/(1xx^2)); fibo[10] ... TypeError: Unable to coerce 0.000000000000000 (<type 'sage.rings.complex_number.ComplexNumber'>) to Rational
Their behaviour is not entirely unreasonable, but it only makes sense if you know that CFiniteSequence
is going to try converting the input to a rational fraction over QQ
.
comment:14 Changed 7 years ago by
 Commit changed from f73e11e1396b68c1668c4808b25edcf38c23163f to a2d51160c58a3466426575b3cf9f724bb6fe66bd
Branch pushed to git repo; I updated commit sha1. New commits:
e7958b0  Merge branch 'ticket/15714' into develop

21fbcca  move to rings/, allow 1/x, subclass from FractionFieldElement

8a1b3a4  add, sub functions

d69aaac  mul, div

a62b72c  be specific about base ring, more doctests

ffea32f  Merge branch 'develop' into ticket/15714

9ee1a05  specify applicability, handle constants, more doctests, better documentation

4218ac8  Merge branch 'develop' into ticket/15714

03f82ba  use pari script default for guessing; safeguards in ctor

a2d5116  last doctests, fix documentation

comment:15 followup: ↓ 30 Changed 7 years ago by
 Status changed from needs_work to needs_review
I refrained from creating a specific parent, as the ring is isomorphic to Laurent polynomial fractions. I specifically allowed ZZ
and QQ
. So Cfinite sequences return their parent as Fraction Field of Univariate Polynomial Ring in x over Rational Field
.
Two guessing algorithms are implemented, BerlekampMassey and LLL (faster,default).
An improvement in clarity could be to replace the internal implementation via vanilla polyniomals by Laurent polyniomals (#11726).
I think the math is pretty standard, though I know of no paper about the isomorphism. If I knew algebra better I would write a paper.
comment:16 Changed 7 years ago by
 Cc rws removed
 Description modified (diff)
comment:17 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:18 Changed 7 years ago by
 Status changed from needs_review to needs_work
comment:19 Changed 7 years ago by
 Commit changed from a2d51160c58a3466426575b3cf9f724bb6fe66bd to 38dd6d0148e92c45dceafcf75f9685b7adec2708
comment:20 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:21 Changed 7 years ago by
 Description modified (diff)
comment:22 Changed 7 years ago by
 Status changed from needs_review to needs_work
The recent move to abandon pexpect demands that the pari script in this patch should be replaced by code using libpari.
comment:23 Changed 7 years ago by
 Status changed from needs_work to needs_review
That demand should not hold up the ticket.
comment:24 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:25 Changed 6 years ago by
 Branch changed from u/rws/ticket/15714 to public/ticket/15714
 Commit changed from 38dd6d0148e92c45dceafcf75f9685b7adec2708 to c14c8a38eddfba9708081e561351a80c6f539821
comment:26 Changed 6 years ago by
 Commit changed from c14c8a38eddfba9708081e561351a80c6f539821 to dbc2c17b8b79211e43d3454fdba86151f7fc51e6
Branch pushed to git repo; I updated commit sha1. New commits:
dbc2c17  trac #15714 one more TESTS::

comment:27 Changed 6 years ago by
 Commit changed from dbc2c17b8b79211e43d3454fdba86151f7fc51e6 to c44cd18aa990bb4bd3bc6a7e362c1cec1b17eb1a
Branch pushed to git repo; I updated commit sha1. New commits:
c44cd18  trac #15714 add doctest missing for sub

comment:28 Changed 6 years ago by
Frédéric, you seem to have had a good look at the code, why not do a review?
comment:29 Changed 6 years ago by
 Commit changed from c44cd18aa990bb4bd3bc6a7e362c1cec1b17eb1a to 0656d07dfa6dfa57f78fb1c2cfb7572a3c842801
comment:30 in reply to: ↑ 15 ; followup: ↓ 31 Changed 6 years ago by
Replying to rws:
I refrained from creating a specific parent, as the ring is isomorphic to Laurent polynomial fractions. I specifically allowed
ZZ
andFraction Field of Univariate Polynomial Ring in x over Rational Field
.
I haven't looked at the new code, but I really doubt that this is a good idea: do you really want, say, the sum of a CFiniteSequence and an integer to return a rational function?!
comment:31 in reply to: ↑ 30 ; followup: ↓ 32 Changed 6 years ago by
Replying to mmezzarobba:
I haven't looked at the new code, but I really doubt that this is a good idea: do you really want, say, the sum of a CFiniteSequence and an integer to return a rational function?!
Nowhere is a function returned. The type remains a polynomial fraction.
comment:32 in reply to: ↑ 31 Changed 6 years ago by
Replying to rws:
Nowhere is a function returned. The type remains a polynomial fraction.
Yes, that's what I mean by rational function.
comment:33 followup: ↓ 34 Changed 6 years ago by
Please compare:
sage: fr = (x/(1+x)).fraction(QQ) sage: 1+fr (2*x + 1)/(x + 1) sage: type(_) <class 'sage.rings.fraction_field_element.FractionFieldElement_1poly_field'> sage: fr+1 (2*x + 1)/(x + 1) sage: type(_) <class 'sage.rings.fraction_field_element.FractionFieldElement_1poly_field'>
versus
sage: R.<x> = PolynomialRing(QQ, 'x') sage: s = CFiniteSequence(x/(1+x)) /home/ralf/sage/local/lib/python2.7/sitepackages/sage/rings/cfinite_sequence.py:212: DeprecationWarning: This method is deprecated. See http://trac.sagemath.org/16201 for details. R.set_default_prec(alen) sage: s Cfinite sequence, generated by x/(x + 1) sage: 1+s (2*x + 1)/(x + 1) sage: s+1 Cfinite sequence, generated by (2*x + 1)/(x + 1) sage: CFiniteSequence(1)+s Cfinite sequence, generated by (2*x + 1)/(x + 1)
What do yu think is wrong there? (Will fix the deprecation warning)
comment:34 in reply to: ↑ 33 ; followup: ↓ 36 Changed 6 years ago by
Replying to rws:
sage: R.<x> = PolynomialRing(QQ, 'x') sage: s = CFiniteSequence(x/(1+x)) /home/ralf/sage/local/lib/python2.7/sitepackages/sage/rings/cfinite_sequence.py:212: DeprecationWarning: This method is deprecated. See http://trac.sagemath.org/16201 for details. R.set_default_prec(alen) sage: s Cfinite sequence, generated by x/(x + 1) sage: 1+s (2*x + 1)/(x + 1) sage: s+1 Cfinite sequence, generated by (2*x + 1)/(x + 1) sage: CFiniteSequence(1)+s Cfinite sequence, generated by (2*x + 1)/(x + 1)What do yu think is wrong there? (Will fix the deprecation warning)
I don't think that's how sage objects are supposed to behave! I'd expect the result of 1+s
not do depend on the order. Moreover, I'd expect that things like 1.0+s
or s+s'
where s'
is another type of sequence can be made to work in the long run even if they don't all work yet.
comment:35 Changed 6 years ago by
 Commit changed from 0656d07dfa6dfa57f78fb1c2cfb7572a3c842801 to 6186c9f5501ce9411fcf6d53d88a9b331b15568c
comment:36 in reply to: ↑ 34 ; followup: ↓ 37 Changed 6 years ago by
Replying to mmezzarobba:
I don't think that's how sage objects are supposed to behave! I'd expect the result of
1+s
not do depend on the order.
Tell you what: I'm working incrementally. I won't add the feature unless you review what is already there.
comment:37 in reply to: ↑ 36 ; followup: ↓ 38 Changed 6 years ago by
Replying to rws:
Replying to mmezzarobba:
I don't think that's how sage objects are supposed to behave! I'd expect the result of
1+s
not do depend on the order.Tell you what: I'm working incrementally. I won't add the feature unless you review what is already there.
I'm not interested in just reviewing what is already there because I don't feel able to judge whether it's a step towards a proper solution or in the wrong direction. I would be interested in implementing the parent myself (and review your commits along the way) if I have timebut that's a big if, unfortunately.
comment:38 in reply to: ↑ 37 ; followup: ↓ 43 Changed 6 years ago by
Replying to mmezzarobba:
I would be interested in implementing the parent myself...
You have my support for that.
comment:39 Changed 6 years ago by
 Commit changed from 6186c9f5501ce9411fcf6d53d88a9b331b15568c to 4787c030ffbd81d04c61ea2c525064c5a5dffed1
comment:40 Changed 6 years ago by
 Cc VivianePons added
Hi,
I just came across this code and I'm willing to review/fix whatever is left cause I would really like to see that into Sage!
I do agree with the comments on the parent. I find it really weird that the parent is the fraction field. Look at this:
sage: R.<x> = QQ[] sage: fibo = CFiniteSequence(x/(1xx^2)) sage: f = x/(1xx^2) sage: f == fibo True sage: fibo == f Traceback (most recent call last): ... AttributeError: 'FractionFieldElement_1poly_field' object has no attribute 'ogf'
Actually, do we really need the CFiniteSequence to extend FractionFieldElement?? What method do we use from FractionFieldElement?? It seems to me that even if a sequence is represented by a fraction, they are two complete different objects.
comment:41 Changed 6 years ago by
You're welcome. This was my early attempt at parenting Sage objects, so there is no particular reason for any oddities. Meanwhile I found that the guess
algorithm "sage"
is less general than "pari"
so you might want to change the default, too. I'll gladly review any additions you make.
comment:42 Changed 6 years ago by
 Commit changed from 4787c030ffbd81d04c61ea2c525064c5a5dffed1 to 504eb03cb625675b1e431bb20ebeb9a414b03ad0
comment:43 in reply to: ↑ 38 Changed 6 years ago by
I have changed the architecture so that CFinite Sequences are no longer sub classes of fraction field elements. Instead, they just store the ogf and belong to their own ring with a proper parent and everything.
I think the new implementation is much cleaner and it's addressing the issues that had been raised before: the behavior and coercions are much more consistent.
Also, it actually makes things easy for the user as you can write directly
sage: CFiniteSequence(1+x) Finite sequence [1, 1], offset = 0
even if x
is a symbolic variable, it gets transformed into a proper fraction field element and the result still has the right parent and everything.
Someone can start reviewing my changes, rws I guess and also mmezzarobba (or whoever wants to look at it).
I still haven't recompiled the doc but I will do shortly.
comment:44 Changed 6 years ago by
 Commit changed from 504eb03cb625675b1e431bb20ebeb9a414b03ad0 to f1eebe73152283061a1366abc2a7839325febae7
Branch pushed to git repo; I updated commit sha1. New commits:
f1eebe7  Fixing doc and tests

comment:45 Changed 6 years ago by
 Commit changed from f1eebe73152283061a1366abc2a7839325febae7 to a31adf78dc4a728de6845dd671521c4d771d3ab2
comment:46 Changed 6 years ago by
 Reviewers set to Ralf Stephan
Nice work! I think this is fine. So someone just needs to look over this last commit, where I fixed the default guessing method. Also, since you while adapting the original code also reviewed it, you should insert your name in the Reviewers field.
Having this finally in mainstream Sage would motivate me to complete the already existing code for automated closed form output.
comment:47 Changed 6 years ago by
Luca should be Lucas, I think.
I have also noted some alignement problems at the beginning of
class CFiniteSequence(FieldElement)
comment:48 Changed 6 years ago by
 Commit changed from a31adf78dc4a728de6845dd671521c4d771d3ab2 to a0aba76ccc6636ca0acb61fbcbde69fe5e1f16f9
Branch pushed to git repo; I updated commit sha1. New commits:
a0aba76  15714: cosmetics

comment:49 Changed 6 years ago by
 Milestone changed from sage6.4 to sage6.8
please use ....:
for doctest continuation (see patchbot report)
comment:50 Changed 6 years ago by
 Commit changed from a0aba76ccc6636ca0acb61fbcbde69fe5e1f16f9 to f81de8b0757027bdd00357aca55bf67799633803
Branch pushed to git repo; I updated commit sha1. New commits:
f81de8b  15714: cosmetics

comment:51 Changed 6 years ago by
 Commit changed from f81de8b0757027bdd00357aca55bf67799633803 to 84c909de109ee7c78cfd07eb320c71d364b8e25a
Branch pushed to git repo; I updated commit sha1. New commits:
84c909d  Fixing a doc output

comment:52 Changed 6 years ago by
I've recompiled the doc and tests and everything seems fine now. The problems reported by Chapoton have been fixed. From my point of view, this is all good. Maybe someone else could give green flag? Anyway, if nobody complains in the near future, I'll move this to positive review.
comment:53 followup: ↓ 55 Changed 6 years ago by
 Status changed from needs_review to positive_review
As you are positive, and your own last commit is fine, and a recent patchbot run passed, I'll set positive myself. Please add yourself to the reviewers, too. Marc?
comment:54 Changed 6 years ago by
 Reviewers changed from Ralf Stephan to Ralf Stephan, Viviane Pons
comment:55 in reply to: ↑ 53 Changed 6 years ago by
Replying to rws:
As you are positive, and your own last commit is fine, and a recent patchbot run passed, I'll set positive myself. Please add yourself to the reviewers, too. Marc?
Sorry, I don't have time to have a look now. But if you both are happy with the current code, I guess all is fine!
comment:56 Changed 6 years ago by
 Branch changed from public/ticket/15714 to 84c909de109ee7c78cfd07eb320c71d364b8e25a
 Resolution set to fixed
 Status changed from positive_review to closed
Please comment on the interface/documentation
New commits:
skeleton interface