gfun[rectoproc] - convert a recurrence into a function

Description

• The procedure outputs a Maple procedure that, given a non negative integer n as input, gives the n-th term u(n) of the linear recurrence.
• If the optional argument remember is supplied, the procedure returned will use option remember.
• If the optional argument list is supplied, the procedure returned will compute the list [u(0),...,u(n)]. In this case it will run in a linear number of arithmetic operations.
• One of the optional arguments remember or list should be given each time one needs a large number of values of the sequence. When the first terms of the recurrence are not explicitly supplied, they are represented symbolically.
• If the optional argument plain is supplied, the procedure returned will "unroll" the recurrence relation using a plain loop, even in cases where more efficient algorithms are supported. This is allows to use the resulting procedure with evalhf, the CodeGeneration package, and other functions that do not support all Maple objects or language features.
• If the optional argument params=[a,b,...] is given then the procedure will take as input n, a, b,...
• When the coefficients of the recurrence are nonconstant polynomials the returned procedure will run in quasi-linear time and space if the remember option is not specified.
• When the coefficients are constant, the procedure will run in logarithmic number of arithmetic operations and without wasting extra space if the remember option is not specified.
• If the optional argument evalfun=fname is given, then the specified procedure is used in the generated code as an evaluation rule. Extra arguments can be passed to the procedure with options preargs=[c,d,...] and postargs=[e,f,...]. Names declared in preargs and postargs may appear in the argument sequence of the generated procedure if they are also declared with the option params. The function is mapped over initial conditions and it is evaluated before procedure generation if the option evalinicond is supplied.
• The option whilecond=boolean_expr defines a condition that is checked at each iteration of the loop of the generated procedure. The condition is represented by a boolean expression that may be function of n, u(n-k) for any positive integer k and function of the names declared in params, preargs and postargs. Execution stops when the condition turns true. This option does not impact initial conditions.
• The option errorcond=boolean_expr defines a condition that is checked at each iteration of the loop of the generated procedure. The condition is represented by a boolean expression that may be function of n, u(n-k) for any positive integer k in 0..ord - where ord is the order of the recurrence - and function of the names declared in params, preargs and postargs. An error is thrown when the condition turns true.
• The option extralocal=[g,h,...] allows to declare and initialize extra local variables. g, h, ... must be either symbols or equations in the form symbol=expression, in which case the expression is used for initialization.
• The option nosymbolsubs disables the name substitution that occurs for the parameters (declared with the option params). This means that the symbols that are used in the generated procedures are the same as the symbols used in the input recurrence. By default, the symbols that are used in the generated procedures are gathered in the global table gfun/rectoproc/symbol.
• The option index makes the generated procedure return the list [n,u(n)]. This is useful in conjunction with whilecond.
• The option rhs=expression allows to specify a right hand side of the recurrence that does not have to be a polynomial. The right hand side may be function of n and of the names declared in the options params, preargs and postargs.

Examples

Fibonacci numbers

We can create different types of programs to generate Fibonacci numbers that are tailored to certain memory or time requirements.

The most obvious procedure is recursive and "remembers" values that are already computed.

> fiborec:={f(i)=f(i-1)+f(i-2),f(0)=1,f(1)=1};

> with(gfun):
fib1:=rectoproc(fiborec,f(i),remember);

> fib1(100);

To create a program which computes and lists the first n terms of the recurrence, we use the list option.

> fib2:=rectoproc(fiborec,f(i),list);

> fib2(10);

To create a program that is more space conscious we avoid the remember option. In this case the program exploits the fact that the recurrence has constant coefficients for extra efficiency.

> fib3:=rectoproc(fiborec,f(i));

> fib3(100);

> fib3(1000);

An example of right-hand side: nested procedures

This example shows how terms of nested recurrences can be computed. The first sequence is first converted into a procedure:

> rec_u:={u(n+2)*(n^2+n+1)+u(n+1)*(n-2)+u(n)*n,u(0)=1,u(1)=2};

> u_n := rectoproc(rec_u,u(n),remember);

The second sequence is defined by

> rec_v:=v(n+3)*(n+4)+v(n+1)*(n^2+2*n)=u(n+1)-n*u(n);

> ini_v:={v(0)=1,v(1)=2,v(2)=3};

The procedure computing v(n) is now generated

> v_n:=rectoproc({op(1,rec_v)}union ini_v,v(n),rhs=subs(u=u_n,op(2,rec_v)),list);

Computation of 10 first terms:

> v_n(9);

Applying a function at each iteration

We illustrate several ways to compute numerical values of the sequence defined by the following recurrence:

> rec := { u(n+2)*(n+1) + u(n)*(n^2+1),u(0)=sin(1),u(1)=cos(1)};

If hardware floating point numbers give a sufficient accuracy, then it is best to produce the procedure and then call evalhf on it:

> p:=subsop(4=NULL,rectoproc(rec,u(n),'plain'));

> evalhf(p(100));

If more precision is required, then evalf can be applied at each iteration using

> p2:=rectoproc(rec,u(n),evalfun='evalf');

> Digits:=30: p2(100);

It is also possible to give the precision as an argument:

> p3 := rectoproc(rec,u(n),evalfun='evalf',params=[d],postargs=[d]);

> p3(100,40);

Extra local variables

The option extralocal is useful when the values of some parameters are not known until the procedure is executed. In the example below, the recurrence is provided with generic intial conditions. The values of these initial conditions are computed at execution-time.

> rec := { u(n)*n + u(n+2),u(0)=A,u(1)=B}:
p := rectoproc(rec,u(n),params=[p],extralocal=[A='f'(p),B='g'(A,p)]);

See Also

gfun, remember, nth_term, diffeqtoproc