Opened 6 years ago

Closed 5 years ago

#15714 closed enhancement (fixed)

implement CFiniteSequence

Reported by: rws Owned by: rws
Priority: major Milestone: sage-6.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) Commit: 84c909de109ee7c78cfd07eb320c71d364b8e25a
Dependencies: Stopgaps:

Description (last modified by rws)

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 6 years ago by rws

  • Description modified (diff)

comment:2 Changed 6 years ago by rws

  • Description modified (diff)

comment:3 Changed 6 years ago by rws

  • 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 6 years ago by rws

  • Commit set to 9d8a0eb2b073cb00a68218ff9a6246b880d500b7

Please comment on the interface/documentation


New commits:

9d8a0ebskeleton interface
Last edited 6 years ago by rws (previous) (diff)

comment:5 Changed 6 years ago by burcin

  • Cc burcin added

comment:6 Changed 6 years ago by mmezzarobba

  • Cc mmezzarobba added

comment:7 Changed 6 years ago by git

  • Commit changed from 9d8a0eb2b073cb00a68218ff9a6246b880d500b7 to 70a29e1f99da5f6bf4d3a465ab26a79b6c9575c2

Branch pushed to git repo; I updated commit sha1. New commits:

70a29e1core functionality

comment:8 Changed 6 years ago by git

  • Commit changed from 70a29e1f99da5f6bf4d3a465ab26a79b6c9575c2 to 6df1fc6a4e7027facf3835574ba893b8af641d0e

Branch pushed to git repo; I updated commit sha1. New commits:

6df1fc6guess(), random_element(), some refactoring

comment:9 Changed 6 years ago by git

  • Commit changed from 6df1fc6a4e7027facf3835574ba893b8af641d0e to 9095be01500c51a0a32b0ffe987dc94a32fd4b96

Branch pushed to git repo; I updated commit sha1. New commits:

9095be0ref doc completed; coefficients(), slicing added

comment:10 Changed 6 years ago by git

  • Commit changed from 9095be01500c51a0a32b0ffe987dc94a32fd4b96 to f73e11e1396b68c1668c4808b25edcf38c23163f

Branch pushed to git repo; I updated commit sha1. New commits:

f73e11ehandle ogf > 1

comment:11 Changed 6 years ago by rws

  • Authors set to rws
  • Description modified (diff)
  • Keywords sequence added
  • Status changed from new to needs_review
  • Summary changed from generalize BinaryRecurrenceSequence to implement CFiniteSequence

comment:12 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:13 Changed 6 years ago by mmezzarobba

  • 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 C-finite 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—C-finite 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 C-Finite 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/(1-x-x^2)); fibo[10]
55
sage: R.<x> = GF(3)[]; fibo = CFiniteSequence(x/(1-x-x^2)); fibo[10]
...
ValueError: Cannot convert to CFiniteSequence.
sage: R.<x> = CC[]; fibo = CFiniteSequence(x/(1-x-x^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.

Last edited 6 years ago by mmezzarobba (previous) (diff)

comment:14 Changed 6 years ago by git

  • Commit changed from f73e11e1396b68c1668c4808b25edcf38c23163f to a2d51160c58a3466426575b3cf9f724bb6fe66bd

Branch pushed to git repo; I updated commit sha1. New commits:

e7958b0Merge branch 'ticket/15714' into develop
21fbccamove to rings/, allow 1/x, subclass from FractionFieldElement
8a1b3a4add, sub functions
d69aaacmul, div
a62b72cbe specific about base ring, more doctests
ffea32fMerge branch 'develop' into ticket/15714
9ee1a05specify applicability, handle constants, more doctests, better documentation
4218ac8Merge branch 'develop' into ticket/15714
03f82bause pari script default for guessing; safeguards in ctor
a2d5116last doctests, fix documentation

comment:15 follow-up: Changed 6 years ago by rws

  • 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 C-finite sequences return their parent as Fraction Field of Univariate Polynomial Ring in x over Rational Field.

Two guessing algorithms are implemented, Berlekamp-Massey 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 6 years ago by rws

  • Authors changed from rws to Ralf Stephan
  • Cc rws removed
  • Description modified (diff)

comment:17 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:18 Changed 6 years ago by rws

  • Status changed from needs_review to needs_work

comment:19 Changed 6 years ago by git

  • Commit changed from a2d51160c58a3466426575b3cf9f724bb6fe66bd to 38dd6d0148e92c45dceafcf75f9685b7adec2708

Branch pushed to git repo; I updated commit sha1. New commits:

27c7f64Merge branch 'develop' into t/15714/ticket/15714
1e45c8315714 apparently Laurent polys do work now as input
38dd6d015714: fix corner cases; improve recurrence representation, refactor its code

comment:20 Changed 6 years ago by rws

  • Status changed from needs_work to needs_review

comment:21 Changed 6 years ago by rws

  • Description modified (diff)

comment:22 Changed 6 years ago by rws

  • 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 6 years ago by rws

  • Status changed from needs_work to needs_review

That demand should not hold up the ticket.

comment:24 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:25 Changed 5 years ago by chapoton

  • Branch changed from u/rws/ticket/15714 to public/ticket/15714
  • Commit changed from 38dd6d0148e92c45dceafcf75f9685b7adec2708 to c14c8a38eddfba9708081e561351a80c6f539821

I have had a look and corrected a few little things. Now pep8 compliant.


New commits:

74694aaMerge branch 'u/rws/ticket/15714' into 6.5.b0
c14c8a3trac #15174 reviewer commit

comment:26 Changed 5 years ago by git

  • Commit changed from c14c8a38eddfba9708081e561351a80c6f539821 to dbc2c17b8b79211e43d3454fdba86151f7fc51e6

Branch pushed to git repo; I updated commit sha1. New commits:

dbc2c17trac #15714 one more TESTS::

comment:27 Changed 5 years ago by git

  • Commit changed from dbc2c17b8b79211e43d3454fdba86151f7fc51e6 to c44cd18aa990bb4bd3bc6a7e362c1cec1b17eb1a

Branch pushed to git repo; I updated commit sha1. New commits:

c44cd18trac #15714 add doctest missing for sub

comment:28 Changed 5 years ago by rws

Frédéric, you seem to have had a good look at the code, why not do a review?

comment:29 Changed 5 years ago by git

  • Commit changed from c44cd18aa990bb4bd3bc6a7e362c1cec1b17eb1a to 0656d07dfa6dfa57f78fb1c2cfb7572a3c842801

Branch pushed to git repo; I updated commit sha1. New commits:

7e706cbMerge branch 'develop' into t/15714/public/ticket/15714
0656d0715714: change default guessing algorithm to 'sage'; guessing of finite sequences no longer supported

comment:30 in reply to: ↑ 15 ; follow-up: Changed 5 years ago by mmezzarobba

Replying to rws:

I refrained from creating a specific parent, as the ring is isomorphic to Laurent polynomial fractions. I specifically allowed ZZ and QQ. So C-finite sequences return their parent as Fraction 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 ; follow-up: Changed 5 years ago by rws

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 5 years ago by mmezzarobba

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 follow-up: Changed 5 years ago by rws

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/site-packages/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
C-finite sequence, generated by x/(x + 1)
sage: 1+s
(2*x + 1)/(x + 1)
sage: s+1
C-finite sequence, generated by (2*x + 1)/(x + 1)
sage: CFiniteSequence(1)+s
C-finite 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 ; follow-up: Changed 5 years ago by mmezzarobba

Replying to rws:

sage: R.<x> = PolynomialRing(QQ, 'x')
sage: s = CFiniteSequence(x/(1+x))
/home/ralf/sage/local/lib/python2.7/site-packages/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
C-finite sequence, generated by x/(x + 1)
sage: 1+s
(2*x + 1)/(x + 1)
sage: s+1
C-finite sequence, generated by (2*x + 1)/(x + 1)
sage: CFiniteSequence(1)+s
C-finite 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 5 years ago by git

  • Commit changed from 0656d07dfa6dfa57f78fb1c2cfb7572a3c842801 to 6186c9f5501ce9411fcf6d53d88a9b331b15568c

Branch pushed to git repo; I updated commit sha1. New commits:

34ed393Merge branch 'develop' into t/15714/public/ticket/15714
6186c9fMerge branch 'develop' into t/15714/public/ticket/15714; fix deprecated code

comment:36 in reply to: ↑ 34 ; follow-up: Changed 5 years ago by 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.

comment:37 in reply to: ↑ 36 ; follow-up: Changed 5 years ago by mmezzarobba

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 time--but that's a big if, unfortunately.

comment:38 in reply to: ↑ 37 ; follow-up: Changed 5 years ago by rws

Replying to mmezzarobba:

I would be interested in implementing the parent myself...

You have my support for that.

comment:39 Changed 5 years ago by git

  • Commit changed from 6186c9f5501ce9411fcf6d53d88a9b331b15568c to 4787c030ffbd81d04c61ea2c525064c5a5dffed1

Branch pushed to git repo; I updated commit sha1. New commits:

43f3c05Merge branch 'develop' into t/15714/public/ticket/15714
4787c0315714: non-ascii in literature, huh why not?

comment:40 Changed 5 years ago by VivianePons

  • 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/(1-x-x^2))
sage: f = x/(1-x-x^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 5 years ago by rws

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 5 years ago by git

  • Commit changed from 4787c030ffbd81d04c61ea2c525064c5a5dffed1 to 504eb03cb625675b1e431bb20ebeb9a414b03ad0

Branch pushed to git repo; I updated commit sha1. New commits:

b8c7b81Merge remote-tracking branch 'origin/public/ticket/15714' into local-15714
504eb03Changing the structure so that CFiniteSequences get a proper parent.

comment:43 in reply to: ↑ 38 Changed 5 years ago by VivianePons

  • Authors changed from Ralf Stephan to Ralf Stephan, Viviane Pons

I have changed the architecture so that C-Finite 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 5 years ago by git

  • Commit changed from 504eb03cb625675b1e431bb20ebeb9a414b03ad0 to f1eebe73152283061a1366abc2a7839325febae7

Branch pushed to git repo; I updated commit sha1. New commits:

f1eebe7Fixing doc and tests

comment:45 Changed 5 years ago by git

  • Commit changed from f1eebe73152283061a1366abc2a7839325febae7 to a31adf78dc4a728de6845dd671521c4d771d3ab2

Branch pushed to git repo; I updated commit sha1. New commits:

f8906caMerge branch 'develop' into t/15714/public/ticket/15714
a31adf715714: fix shortcomings of default guessing method

comment:46 Changed 5 years ago by rws

  • 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 5 years ago by chapoton

Luca should be Lucas, I think.

I have also noted some alignement problems at the beginning of class CFiniteSequence(FieldElement)

comment:48 Changed 5 years ago by git

  • Commit changed from a31adf78dc4a728de6845dd671521c4d771d3ab2 to a0aba76ccc6636ca0acb61fbcbde69fe5e1f16f9

Branch pushed to git repo; I updated commit sha1. New commits:

a0aba7615714: cosmetics

comment:49 Changed 5 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-6.8

please use ....: for doctest continuation (see patchbot report)

comment:50 Changed 5 years ago by git

  • Commit changed from a0aba76ccc6636ca0acb61fbcbde69fe5e1f16f9 to f81de8b0757027bdd00357aca55bf67799633803

Branch pushed to git repo; I updated commit sha1. New commits:

f81de8b15714: cosmetics

comment:51 Changed 5 years ago by git

  • Commit changed from f81de8b0757027bdd00357aca55bf67799633803 to 84c909de109ee7c78cfd07eb320c71d364b8e25a

Branch pushed to git repo; I updated commit sha1. New commits:

84c909dFixing a doc output

comment:52 Changed 5 years ago by VivianePons

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 follow-up: Changed 5 years ago by rws

  • 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 5 years ago by VivianePons

  • Reviewers changed from Ralf Stephan to Ralf Stephan, Viviane Pons

comment:55 in reply to: ↑ 53 Changed 5 years ago by mmezzarobba

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 5 years ago by vbraun

  • Branch changed from public/ticket/15714 to 84c909de109ee7c78cfd07eb320c71d364b8e25a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.