convert a recurrence into a procedure - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Factorization and Solving Equations : LREtools : LREtools/REtoproc

LREtools[REtoproc] - convert a recurrence into a procedure

Calling Sequence

REtoproc(problem, options)

Parameters

problem

-

problem

options

-

optional arguments described below

Description

• 

This procedure returns a Maple procedure that, given a non-negative integer n as input, gives the nth term of the linear recurrence.

• 

If the argument 'remember' or 'remember'=true is specified, then the procedure will compute the sequence via a recursive procedure using option remember. By default, 'remember'=false and the sequence is computed iteratively.

• 

The argument 'remember' should be given when one needs a large number of values of the sequence.

• 

When 'remember'=false and the coefficients of the recurrence are nonconstant polynomials, the returned procedure will run in a straight loop, using a linear number of arithmetic operations and without wasting extra space.

• 

When 'remember'=false and the coefficients are constant, the procedure will employ a binary-based optimization strategy (for large index values only), and runs with a logarithmic number of arithmetic operations. This optimization can be disabled by specifying constantoptimize=false.

• 

When 'remember'=false, by default the initial terms of the recurrence are embedded in the code. This can be changed to put the initial terms of the recurrence in the remember table by specifying initialremember=true.

• 

When the first terms of the recurrence are not explicitly supplied, they are represented symbolically.

• 

The command with(LREtools,REtoproc) allows the use of the abbreviated form of this command.

Examples

withLREtools:interfaceverboseproc=3:

fib := REtoproc(f(i)=f(i-1)+f(i-2),f(i),{f(0)=0,f(1)=1});

fib:=procn::nonnegint&comma; $locali&comma;u0&comma;u1&comma;u2&comma;a&comma;res&comma;l&semi;u0:=0&semi;u1:=1&semi;ifn&equals;0thenu0elifn&equals;1thenu1elifn<=44thenforifrom2ton1dou2:=u0&plus;u1&semi;u0:=u1&semi;u1:=u2end do&semi;u0&plus;u1elsea:=array1..2&comma;1..2&comma;1&comma;1&comma;1&comma;0&semi;res:=array1..2&comma;u1&comma;u0&semi;l:=convertn1&comma;&apos;base&apos;&comma;2&semi;ifl&lsqb;1&rsqb;&equals;1thenres:=array1..2&comma;1&equals;a&lsqb;1&comma;1&rsqb;&ast;res&lsqb;1&rsqb;&plus;a&lsqb;1&comma;2&rsqb;&ast;res&lsqb;2&rsqb;&comma;2&equals;a&lsqb;2&comma;1&rsqb;&ast;res&lsqb;1&rsqb;&plus;a&lsqb;2&comma;2&rsqb;&ast;res&lsqb;2&rsqb;end if&semi;ifl&equals;1thenres&lsqb;1&rsqb;elseforiinl&lsqb;2..&minus;2&rsqb;doa:=array1..2&comma;1..2&comma;2&comma;2&equals;a&lsqb;1&comma;2&rsqb;&ast;a&lsqb;2&comma;1&rsqb;&plus;a&lsqb;2&comma;2&rsqb;&Hat;2&comma;1&comma;1&equals;a&lsqb;1&comma;1&rsqb;&Hat;2&plus;a&lsqb;1&comma;2&rsqb;&ast;a&lsqb;2&comma;1&rsqb;&comma;2&comma;1&equals;a&lsqb;1&comma;1&rsqb;&ast;a&lsqb;2&comma;1&rsqb;&plus;a&lsqb;2&comma;1&rsqb;&ast;a&lsqb;2&comma;2&rsqb;&comma;1&comma;2&equals;a&lsqb;1&comma;1&rsqb;&ast;a&lsqb;1&comma;2&rsqb;&plus;a&lsqb;1&comma;2&rsqb;&ast;a&lsqb;2&comma;2&rsqb;&semi;ifi&equals;1thenres:=array1..2&comma;1&equals;a&lsqb;1&comma;1&rsqb;&ast;res&lsqb;1&rsqb;&plus;a&lsqb;1&comma;2&rsqb;&ast;res&lsqb;2&rsqb;&comma;2&equals;a&lsqb;2&comma;1&rsqb;&ast;res&lsqb;1&rsqb;&plus;a&lsqb;2&comma;2&rsqb;&ast;res&lsqb;2&rsqb;end ifend do&semi;a&lsqb;1&comma;1&rsqb;&Hat;2&plus;a&lsqb;1&comma;2&rsqb;&ast;a&lsqb;2&comma;1&rsqb;&ast;res&lsqb;1&rsqb;&plus;a&lsqb;1&comma;1&rsqb;&ast;a&lsqb;1&comma;2&rsqb;&plus;a&lsqb;1&comma;2&rsqb;&ast;a&lsqb;2&comma;2&rsqb;&ast;res&lsqb;2&rsqb;end ifend ifend proc

(1)

fib100

354224848179261915075

(2)

fib2 := REtoproc(f(i)=f(i-1)+f(i-2),f(i),{f(0)=0,f(1)=1},'remember');

fib2:=procn::nonnegint&comma; $optionremember&semi;procnamen2&plus;procnamen1end proc#(0) = 0#(1) = 1

(3)

fib2100

354224848179261915075

(4)

rec := REtoproc(f(i)=i^2*f(i-1)+f(i-2),f(i),{},'remember');

rec:=procn::nonnegint&comma; $optionremember&semi;n&Hat;2&ast;procnamen1&plus;procnamen2end proc#(0) = f(0)#(1) = f(1)

(5)

rec100

9058477158744039108901484875567483833514619274297483550856232216805415823966784458605109749449017462079827918537250156488348819998559536412999537100386489240766568099262887636990141071242906533135806432242520067765428965147272705161620549611736618446171403767978982293333281882312513474668524116583587067499136325876f1&plus;2203823124569416698291075403023306063089022127683403942005208386556556750073849332403233124551522569729148712230224505771905205727903820151912839068030542989769962446264480000034834468134656141631555555405058769399965103438352643881658179110007643158335872008434125847040069584050780045011709372240155319761920733361f0

(6)

See Also

LREtools[REcreate], RESol, rsolve


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