December 2003 - PURRS-devel

base case assumptions
by Shailesh Humbad 23 Jan '04

23 Jan '04

I am having a problem with the online version of PURRS. I tried it on a recurrence relation derived from an algorithm I'm working on, and the resulting formula is off by one for even n. I believe it may be something to do with our assumptions for the base cases and starting index. Is that something that would affect the results? INPUT: x(n) = x(n-2) + 2*n - 5 for n > 2 x(n) = 0 for n <= 2 OUTPUT: Exact solution for x(n) = -5+x(-2+n)+2*n x(n) = 1/2*n^2+3/2*mod(n,2)+x(mod(n,2))-1/2*mod(n,2)^2-3/2*n RESULTS: (n, x(n) Recurrence, x(n) PURRS) (2, 0, -1) (3, 1, 1) (4, 3, 2) (5, 6, 6) (6, 10, 9) (7, 15, 15) (8, 21, 20) (9, 28, 28) (10, 36, 35) Note that the PURRS result is one less when n is even. However, the formula works when the base cases are x(0) = 1 and x(1) = 0. In the results shown above, my assumption is that both are equal to zero. Thanks and Happy Holidays, Shailesh

2 2

purrs/src Recurrence.cc Recurrence.defs.hh
by Tatiana Zolo 31 Dec '03

31 Dec '03

CVSROOT: /cvs/purrs Module name: purrs Changes by: zolo(a)cs.unipr.it 2003-12-31 17:32:24 Modified files: src : Recurrence.cc Recurrence.defs.hh Log message: Improved the traditional step 3 with the same idea used in the new method: no longer consider all the homogeneous part of the solution, but the step 3 is applied k times (k is the order of the recurrence) on the coefficients of the symbolic initial conditions occurring in the homogeneous part of the recurrence. Other minor improvements. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/src/Recurrence.cc.diff?cvsr… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/src/Recurrence.defs.hh.diff…

1 0

purrs/src Recurrence.cc
by Tatiana Zolo 30 Dec '03

30 Dec '03

CVSROOT: /cvs/purrs Module name: purrs Changes by: zolo(a)cs.unipr.it 2003-12-30 21:54:54 Modified files: src : Recurrence.cc Log message: Fixed a bug in the step 3 of the new verification. Some improvements. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/src/Recurrence.cc.diff?cvsr…

1 0

[Fwd: Re: [PURRS-devel] base case assumptions]
by Roberto Bagnara 30 Dec '03

30 Dec '03

-------- Original Message -------- Subject: Re: [PURRS-devel] base case assumptions Date: Mon, 29 Dec 2003 21:22:03 -0500 From: Shailesh Humbad <humbads(a)alum.mit.edu> To: Roberto Bagnara <bagnara(a)cs.unipr.it> References: <6.0.0.22.0.20031226022754.01ccf318(a)nyip.net> <3FEF09D2.2040706(a)cs.unipr.it> Thanks for confirming my suspicion and for making the research demo available online. It's a very useful tool for those of us who don't have access to Mathematica. By the way, when the base cases are defined and a correction term added to the formula given by PURRS, the solution to the recurrence reduces to [(n-2)*(n-1)]/2. Regards, Shailesh At 11:50 AM 12/28/2003, you wrote: >Shailesh Humbad wrote: >>I am having a problem with the online version of PURRS. >> I tried it on a recurrence relation derived from an algorithm >> I'm working on, and the resulting formula is off by one for even n. >> I believe it may be something to do with our assumptions for the base >> cases and starting index. Is that something that would affect the results? > >Dear Shailesh, > >you are right: the online demo assumes that, for a recurrence of order >k, the initial conditions are given for x(0), ..., x(k-1). >We are working at a revision of our system (that currently is, remember, >only a research prototype) that will allow to specify any set of >initial conditions and special cases. >We will also extend the online demo so as to make this facilities >available through the web. > >>Thanks and Happy Holidays, > >Thanks for your input. >Have a great 2004, > > Roberto Bagnara on behalf of the PURRS team > >-- >Prof. Roberto Bagnara >Computer Science Group >Department of Mathematics, University of Parma, Italy >http://www.cs.unipr.it/~bagnara/ >mailto:bagnara@cs.unipr.it -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it

1 0

purrs/tests heap
by Roberto Bagnara 29 Dec '03

29 Dec '03

CVSROOT: /cvs/purrs Module name: purrs Changes by: roberto(a)cs.unipr.it 2003-12-29 22:19:31 Modified files: tests : heap Log message: Four recurrences marked with `yv'. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/tests/heap.diff?cvsroot=pur…

1 0

purrs/demos purrs_rrs_cgi.cc
by Roberto Bagnara 29 Dec '03

29 Dec '03

CVSROOT: /cvs/purrs Module name: purrs Changes by: roberto(a)cs.unipr.it 2003-12-29 19:13:27 Modified files: demos : purrs_rrs_cgi.cc Log message: Timings are now given in microseconds. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/demos/purrs_rrs_cgi.cc.diff…

1 0

purrs/demos purrs_rrs_cgi.cc
by Roberto Bagnara 29 Dec '03

29 Dec '03

CVSROOT: /cvs/purrs Module name: purrs Changes by: roberto(a)cs.unipr.it 2003-12-29 19:00:21 Modified files: demos : purrs_rrs_cgi.cc Log message: Corrected a bug in the formatting of the results page. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/demos/purrs_rrs_cgi.cc.diff…

1 0

purrs/demos purrs_rrs_cgi.cc
by Roberto Bagnara 29 Dec '03

29 Dec '03

CVSROOT: /cvs/purrs Module name: purrs Changes by: roberto(a)cs.unipr.it 2003-12-29 18:55:46 Modified files: demos : purrs_rrs_cgi.cc Log message: Compute and report both the solution and the verification time. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/demos/purrs_rrs_cgi.cc.diff…

1 0

purrs/src tsc.hh
by Roberto Bagnara 29 Dec '03

29 Dec '03

CVSROOT: /cvs/purrs Module name: purrs Changes by: roberto(a)cs.unipr.it 2003-12-29 18:28:42 Modified files: src : tsc.hh Log message: Be silent. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/src/tsc.hh.diff?cvsroot=pur…

1 0

purrs/src Recurrence.cc
by Tatiana Zolo 29 Dec '03

29 Dec '03

CVSROOT: /cvs/purrs Module name: purrs Changes by: zolo(a)cs.unipr.it 2003-12-29 18:20:12 Modified files: src : Recurrence.cc Log message: Added the label `NEW_VERIFICATION' by default set to 1. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/src/Recurrence.cc.diff?cvsr…

1 0