gfun - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : gfun : gfun/rectoproc

gfun

  

rectoproc

  

convert a recurrence into a function

 

Calling Sequence

Parameters

Description

Examples

Calling Sequence

rectoproc(eqns,u(n), remember, list,params=[a,b,...],<options>)

Parameters

eqns

-

single equation or set of equations

u

-

name; recurrence name

n

-

name; index of recurrence u

remember

-

(optional) name; specify that returned procedure uses option remember

list

-

(optional) name; specify that returned procedure computes the list [u(0), ..., u(n)]

params = [a, b, ...]

-

(optional) names; argument names

evalfun = fname

-

(optional) a function applied at each iteration

preargs=[c, d, ...]

-

(optional) first arguments to this function

postargs=[e, f, ...]

-

(optional) last arguments to this function

evalinicond

-

(optional)

whilecond=boolean_expr

-

(optional) while condition

errorcond=boolean_expr

-

(optional) error condition

index

-

(optional)

rhs=expression

-

(optional)

copyright=string

-

(optional) copyright string to be added to the options

extralocal=[g, h, ...]

-

(optional) names for extra local variables

nosymbolsums

-

(optional)

Description

• 

The rectoproc(eqns, u(n)) command returns a Maple procedure that, given a non-negative integer n as input, returns the nth term u(n) of the linear recurrence.

• 

If remember is specified, the function returns a procedure that uses option remember.

• 

If the optional argument remember is supplied, the procedure returned will use option remember.

• 

If list is specified, the returned procedure computes the list &lsqb;u0,...,un&rsqb;. In this case it runs 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 params=&lsqb;a,b,...&rsqb; is specified, the function returns a procedure that accepts n, a, b,... as input.

• 

If the coefficients of the recurrence are nonconstant polynomials, the returned procedure runs in a linear number of arithmetic operations without using extra space if the remember option is not specified.

• 

If the coefficients are constant, the returned procedure runs in a logarithmic number of arithmetic operations without using 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= &lsqb;c,d,...&rsqb; and postargs= &lsqb;&ExponentialE;,f,...&rsqb;. 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, unk 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, unk 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= &lsqb;g,h,...&rsqb; 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&comma;un. This is useful in conjunction with whilecond.

• 

You should specify remember or list each time a large number of values for the sequence is required.

• 

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

You can create different types of programs to generate Fibonacci numbers that meet certain memory or time requirements.

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

fiborecfi&equals;fi1&plus;fi2&comma;f0&equals;1&comma;f1&equals;1

fiborec:=f0&equals;1&comma;f1&equals;1&comma;fi&equals;fi1&plus;fi2

(1)

withgfun&colon;

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

fib1:=procnoptionremember&semi;procname&minus;2&plus;n&plus;procname&minus;1&plus;nend proc

(2)

fib1100

573147844013817084101

(3)

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:=procnlocali1&comma;loc&semi;loc&lsqb;0&rsqb;:=1&semi;loc&lsqb;1&rsqb;:=1&semi;ifn<0thenerrorindex must be %1 or greater&comma;0elifn&equals;0thenreturnloc&lsqb;0&rsqb;elifn&equals;1thenreturnloc&lsqb;1&rsqb;end if&semi;fori1to&minus;1&plus;ndoloc&lsqb;i1&plus;1&rsqb;:=loc&lsqb;&minus;1&plus;i1&rsqb;&plus;loc&lsqb;i1&rsqb;end do&semi;seqloc&lsqb;i1&rsqb;&comma;i1&equals;0..nend proc

(4)

fib210

1&comma;1&comma;2&comma;3&comma;5&comma;8&comma;13&comma;21&comma;34&comma;55&comma;89

(5)

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:=procnlocali1&comma;loc0&comma;loc1&comma;loc2&comma;tmp2&comma;tmp1&comma;i2&semi;ifn<=44thenloc0:=1&semi;loc1:=1&semi;ifn<0thenerrorindex must be %1 or greater&comma;0elifn&equals;0thenreturnloc0elifn&equals;1thenreturnloc1end if&semi;fori1to&minus;1&plus;ndoloc2:=loc0&plus;loc1&semi;loc0:=loc1&semi;loc1:=loc2end do&semi;loc1elsetmp2:=`Matrix(2, 2, {(1, 1) = 1, (1, 2) = 1, (2, 1) = 1, (2, 2) = 0})`&semi;tmp1:=`Vector(2, {(1) = 1, (2) = 1})`&semi;i2:=convert&minus;1&plus;n&comma;base&comma;2&semi;ifi2&lsqb;1&rsqb;&equals;1thentmp1:=`Vector(2, {(1) = 2, (2) = 1})`end if&semi;fori1insubsop1&equals;&comma;i2dotmp2:=`LinearAlgebra:-MatrixMatrixMultiply`tmp2&comma;tmp2&semi;ifi1&equals;1thentmp1:=`LinearAlgebra:-MatrixVectorMultiply`tmp2&comma;tmp1end ifend do&semi;tmp1&lsqb;1&rsqb;end ifend proc

(6)

fib3100

573147844013817084101

(7)

fib31000

70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

(8)

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_uun&plus;2n2&plus;n&plus;1&plus;un&plus;1n2&plus;unn&comma;u0&equals;1&comma;u1&equals;2

rec_u:=un&plus;2n2&plus;n&plus;1&plus;un&plus;12&plus;n&plus;unn&comma;u0&equals;1&comma;u1&equals;2

(9)

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

u_n:=procnoptionremember&semi;2&ast;procname&minus;2&plus;n&plus;4&ast;procname&minus;1&plus;nprocname&minus;2&plus;n&plus;procname&minus;1&plus;n&ast;n&sol;3&plus;&minus;3&plus;n&ast;nend proc

(10)

The second sequence is defined by

rec_vvn&plus;3n&plus;4&plus;vn&plus;1n2&plus;2n&equals;un&plus;1nun

rec_v:=vn&plus;3n&plus;4&plus;vn&plus;1n2&plus;2n&equals;un&plus;1unn

(11)

ini_vv0&equals;1&comma;v1&equals;2&comma;v2&equals;3

ini_v:=v0&equals;1&comma;v1&equals;2&comma;v2&equals;3

(12)

The procedure computing vn 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);

v_n:=procnlocali1&comma;loc&semi;loc&lsqb;0&rsqb;:=1&semi;loc&lsqb;1&rsqb;:=2&semi;loc&lsqb;2&rsqb;:=3&semi;ifn<0thenerrorindex must be %1 or greater&comma;0elifn&equals;0thenreturnloc&lsqb;0&rsqb;elifn&equals;1thenreturnloc&lsqb;1&rsqb;elifn&equals;2thenreturnloc&lsqb;2&rsqb;end if&semi;fori1from2to&minus;1&plus;ndoloc&lsqb;i1&plus;1&rsqb;:=u_n&minus;1&plus;i1u_n&minus;2&plus;i1&ast;&minus;2&plus;i13&plus;&minus;3&plus;i1&ast;i1&plus;1&ast;loc&lsqb;&minus;1&plus;i1&rsqb;&sol;i1&plus;2end do&semi;seqloc&lsqb;i1&rsqb;&comma;i1&equals;0..nend proc

(13)

Computation of 10 first terms:

v_n9

1&comma;2&comma;3&comma;12&comma;75&comma;179&comma;12549&comma;68031092&comma;16956717199&comma;42369714105

(14)

Applying a function at each iteration

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

recun&plus;2n&plus;1&plus;unn2&plus;1&comma;u0&equals;sin1&comma;u1&equals;cos1

rec:=un&plus;2n&plus;1&plus;unn2&plus;1&comma;u0&equals;sin1&comma;u1&equals;cos1

(15)

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)));

p:=procnlocali1&comma;loc0&comma;loc1&comma;loc2&semi;loc0:=sin1&semi;loc1:=cos1&semi;ifn<0thenerrorindex must be %1 or greater&comma;0elifn&equals;0thenreturnloc0elifn&equals;1thenreturnloc1end if&semi;fori1to&minus;1&plus;ndoloc2:=&minus;5&plus;&minus;3&plus;i1&ast;i1&plus;1&ast;loc0&sol;i1&semi;loc0:=loc1&semi;loc1:=loc2end do&semi;loc1end proc

(16)

evalhfp100

5.277391538696397461076

(17)

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

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

p2:=procnlocali1&comma;loc0&comma;loc1&comma;loc2&semi;loc0:=evalfsin1&semi;loc1:=evalfcos1&semi;ifn<0thenerrorindex must be %1 or greater&comma;0elifn&equals;0thenreturnloc0elifn&equals;1thenreturnloc1end if&semi;fori1to&minus;1&plus;ndoloc2:=evalf&minus;5&plus;&minus;3&plus;i1&ast;i1&plus;1&ast;loc0&sol;i1&semi;loc0:=loc1&semi;loc1:=loc2end do&semi;loc1end proc

(18)

Digits30&colon;p2100

5.277391538696397692062429568961076

(19)

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

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

p3:=procn&comma;b1locali1&comma;loc0&comma;loc1&comma;loc2&semi;loc0:=evalfsin1&comma;b1&semi;loc1:=evalfcos1&comma;b1&semi;ifn<0thenerrorindex must be %1 or greater&comma;0elifn&equals;0thenreturnloc0elifn&equals;1thenreturnloc1end if&semi;fori1to&minus;1&plus;ndoloc2:=evalf&minus;5&plus;&minus;3&plus;i1&ast;i1&plus;1&ast;loc0&sol;i1&comma;b1&semi;loc0:=loc1&semi;loc1:=loc2end do&semi;loc1end proc

(20)

p3100&comma;40

5.2773915386963976920624295689901700868211076

(21)

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 initial conditions. The values of these initial conditions are computed at execution-time.

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

recunn&plus;un&plus;2&comma;u0&equals;A&comma;u1&equals;B&colon;

rectoproc(rec,u(n),params=[p],extralocal=[A='f'(p),B='g'(A,p)]);

procn&comma;b1locali1&comma;loc0&comma;loc1&comma;loc2&comma;xloc1&comma;xloc2&semi;xloc1:=fb1&semi;xloc2:=gxloc1&comma;b1&semi;loc0:=xloc1&semi;loc1:=xloc2&semi;ifn<0thenerrorindex must be %1 or greater&comma;0elifn&equals;0thenreturnloc0elifn&equals;1thenreturnloc1end if&semi;fori1to&minus;1&plus;ndoloc2:=&minus;&minus;1&plus;i1&ast;loc0&semi;loc0:=loc1&semi;loc1:=loc2end do&semi;loc1end proc

(22)

See Also

gfun

procedure

remember

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam