Two comments: 1. Memoization may be the answer, but this is a beautiful
example of recursion, as the 'obvious' route, being far slower.
Two: Years ago I gave a numerical analysis class the problem of fitting a
cubic spline to data where the two extra conditions were specified as the
first and second derivatives at the left end, a thoroughly embedded
unstable process.
The responses were first that the set of linear equations to get from one
spline to the next was an unreasonable request on my part, but with the
data this was trivial, but did result in an absurd result (would you
believe xx10^40). Not more than 15% of the class even looked at the
solution enough to wonder if something might be wrong.
Rather 'you must give me credit, the software ran to a conclusion'
On Sat, 16 Dec 2006,
John Randall wrote:
Although the recurrence does not look especially unstable, it is, as
an analytic solution shows. The general solution g(n) is given by
(h n+1)%(h n)
where
h=:3 : '(a,b,c) +/ . * 3 5 100^y'
and (a,b,c) is determined by the initial conditions up to a nonzero
scalar multiple. Thus
g(n)->100 if c~:0
g(n)->5 if c=0 and b~:0
g(n)->3 if c=0 and b=0
For the initial conditions given, a=b and c=0. Rounding errors using
a 53-bit mantissa cause the recurrence to behave as though c~:0.
As Roger and Raul have indicated, doing the calculation exactly in
rationals will give the correct answer: however, this is not an option
for most practical numerical problems. As Ralph suggests,
restructuring the problem is the solution.
Best wishes,
John
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
