January 2004 - PURRS-devel - BUGSENG Mailman

purrs/demos purrs_rrs_cgi.cc
by Tatiana Zolo 26 Jan '04

26 Jan '04

CVSROOT: /cvs/purrs Module name: purrs Changes by: zolo(a)cs.unipr.it 2004-01-26 09:35:25 Modified files: demos : purrs_rrs_cgi.cc Log message: Allowed the initial conditions also in the case of functional equations (the non-negative numbers are temporary not allowed). Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/demos/purrs_rrs_cgi.cc.diff…

1 0

purrs/src Recurrence.defs.hh Recurrence.cc
by Tatiana Zolo 26 Jan '04

26 Jan '04

CVSROOT: /cvs/purrs Module name: purrs Changes by: zolo(a)cs.unipr.it 2004-01-26 09:35:00 Modified files: src : Recurrence.defs.hh Recurrence.cc Log message: Added the method `compute_solution_functional_equation_on_i_c()'. Improved the method `set_initial_conditions()' so that are allowed initial conditions also in the case of functional equations (the non-negative numbers are temporary not allowed). Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/src/Recurrence.defs.hh.diff… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/src/Recurrence.cc.diff?cvsr…

1 0

purrs/src Recurrence.cc Recurrence.defs.hh glo ...
by Tatiana Zolo 24 Jan '04

24 Jan '04

CVSROOT: /cvs/purrs Module name: purrs Changes by: zolo(a)cs.unipr.it 2004-01-24 20:11:02 Modified files: src : Recurrence.cc Recurrence.defs.hh globals.hh Log message: Used "indices" instead of "indexes" in the documentation. 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… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/src/globals.hh.diff?cvsroot…

1 0

[Fwd: Re: [PURRS-devel] base case assumptions]
by Roberto Bagnara 23 Jan '04

23 Jan '04

-------- Original Message -------- Subject: Re: [PURRS-devel] base case assumptions Date: Fri, 23 Jan 2004 13:55:04 -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> <40116304.6060708(a)cs.unipr.it> Prof. Bagnara, Wow, that is fantastic. I tried it online and it worked. Software that can do math always impresses me greatly. When I use only two conditions, x(0) = 0 and x(1) = 0, I get what looks like old answer, which alternates by 1. When I use x(1)=0 and x(2)=0, I get the right answer. In my notes, I have x(0) as being undefined, as you say, a special case. So I think PURRS is working correctly, because this 2nd order recurrence's two initial conditions are actually x(1)=0 and x(2)=0. For this recurrence, it was more important for me to know the complexity of the solution (i.e. polynomial or exponential) than the exact formula. I believe that in computer science this is usually the case. I don't know how PURRS does approximations, but if no other information could be calculated, then it might be useful if PURRS could determine just the order of the solution. Just of interest, the solution factors to ((n-2)*(n-1))/2. This means it is simple enough to have been arrived at combinatorically, by studying the cases. I think software saves us time, but it makes us lazy ;) Thank you for making this tool available online. Shailesh Dear Shailesh, >we have done significant progress in the development of PURRS, and >this is also reflected in the on-line demo. You should now be able to >use the demo the way you wanted. You can either: > >- specify the right-hand side of the recurrence; >- specify the right-hand side of the recurrence > _and_ any set of initial conditions and special cases. > >In the first case you will obtain the symbolic solution of the >recurrence containing the initial conditions x(i), ..., x(i+k-1) >(where `i' is the first index for which the recurrence is well-defined >and `k' is the order of the recurrence). > >In the second case you obtain the solution of the recurrence with the >specified initial conditions and special cases. > >For instance, in the case of your example > > x(n) = x(n-2) + 2*n - 5 > >you can specify the set of initial conditions (notice that in this case >the recurrence is of the second order and thus PURRS requires at least >2 initial conditions) as, e.g., > > x(0) = 0; x(1) = 0; x(2) = 0 > >obtaining the solution > > x(n) = 1+1/2*n^2-3/2*n > for each n >= 1 > >(x(0) = 0 is considered as a special case). >Standard disclaimer: all this is work in progress, so you could >observe something unexpected results: please do not hesitate to >contact us if you do. Thanks again for your feedback. >All the best > > 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

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
by Tatiana Zolo 23 Jan '04

23 Jan '04

CVSROOT: /cvs/purrs Module name: purrs Changes by: zolo(a)cs.unipr.it 2004-01-23 09:07:16 Modified files: src : Recurrence.cc Log message: Improved the exception's messages in the method `set_initial_conditions()'. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/src/Recurrence.cc.diff?cvsr…

1 0

purrs/tests heap
by Tatiana Zolo 22 Jan '04

22 Jan '04

CVSROOT: /cvs/purrs Module name: purrs Changes by: zolo(a)cs.unipr.it 2004-01-22 16:22:57 Modified files: tests : heap Log message: Set to `M' the mark of recurrences with the right-hand side containing symbolic initial conditions. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/tests/heap.diff?cvsroot=pur…

1 0

purrs/src Recurrence.defs.hh rr_classifier.cc
by Tatiana Zolo 22 Jan '04

22 Jan '04

CVSROOT: /cvs/purrs Module name: purrs Changes by: zolo(a)cs.unipr.it 2004-01-22 16:22:31 Modified files: src : Recurrence.defs.hh rr_classifier.cc Log message: The recurrences with the right-hand side containing symbolic initial conditions are now marked as malformed. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/src/Recurrence.defs.hh.diff… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/src/rr_classifier.cc.diff?c…

1 0

w3purrs/htdocs details.raw
by Tatiana Zolo 22 Jan '04

22 Jan '04

CVSROOT: /cvs/purrs Module name: w3purrs Changes by: zolo(a)cs.unipr.it 2004-01-22 15:48:41 Modified files: htdocs : details.raw Log message: Removed an old remark. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/w3purrs/htdocs/details.raw.diff?c…

1 0

purrs/src verify.cc
by Tatiana Zolo 22 Jan '04

22 Jan '04

CVSROOT: /cvs/purrs Module name: purrs Changes by: zolo(a)cs.unipr.it 2004-01-22 14:14:43 Modified files: src : verify.cc Log message: Minor improvement in the method `verify_finite_order()'. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/src/verify.cc.diff?cvsroot=…

1 0