More Advanced Topics
Some Other topics
Dynamic Programming
Recursive programs are programs that "refer to themselves". Such programs can be very slow because they use a lot of "stack memory". One way to speed them up is by means of "dynamic programming" or "functions that remember their values". The best way to understand this method is by means of an example.
Fast Fibonacci numbers.
Let's compare the following two definitions of the Fibonacci numbers. First we start with a usual recursive definition.
This is very slow and already the 30th Fibonacci number takes a noticeable time to compute. Next, we try "dynamic programing". The definition looks a little strange; note the use of := and = .
Computing even the 50th Fibonacci number takes virtually no time.
We can see the difference between the two definitions by using the function Trace:
The first function repeatedly performs the same computation (see Fib1[3] and Fib2[3] in the output of Trace above).
We can also check what Mathematica knows about the functions Fib1 and Fib2
|
|
The point is that the last definition makes Fib2 remember each value that it has once computed so it never has to compute it again. The result is much better performance at the cost of some memory consumption, of course. This can be recovered by using
Imperative (Procedural) and Functional programming
So far we have considered two programming styles that one can use in Mathematica - rule based and functional. There is also another style, called procedural or imperative. This is the style used by most traditional programming languages, such as C. The characteristic of this style is the use of explicit assignments to variables, and of loops that change the state of a variable. Here is an example of a procedural program which changes the state of a variable x by using assignments:
This can be also written as
Note that Mathematica automatically returns the value of the last argument of ComposedExpression. In most procedural languages no final value would be returned and you need an explicit Return or Print statement Return[x] or Print[x] at the end. In Mathematica you never need these statements for this purpose.
Below is another way to do the same thing, using a Do loop. Note that the Do loop does not return anything, so we need x at the end if we wish to return the value of x.
Mathematica has other procedural loops: While and For. They should be used sparingly, particularly the last one which is very inefficient. In general you can get much better performance from Mathematica by using functional constructions: Nest, Fold and FixedPoint and in version 6, Accumulate.
$
Because in imperative programs assignments are used, one has to be careful not to accidentally use or redefine variables to which values may have been assigned earlier. The best way to protect oneself from this possibility is by means of local variables. Mathematica has three basic constructions for localizing variables: Block, Module and With.
Although inside Block we set the value of x to 1, outside it remained equal to 3. The same will happen if we use Module
Block and Module work in a quite different way. When you localize a variable in Block its value is first stored, then erased, than after Block is exited the old (stored) value is restored. In the case of Module the variables are renamed so that their names do not conflict with any other names. Another construction that localizes variables is With. Note that, unlike in Module and Block, all local variables in With must be initialized so you can't use assignments to local variables in With.
Another important example:
Although foo was definied outside Block, its value inside Block is changed. This does not happen when we use Module:
Thus, Module depends only on the original definition, Block on the evaluation. (Lexical scoping vs dynamic scoping).
Loops and Functional Iteration
Programs written in this style change the values of some variable. In order to get the changed value one has to explicitly evaluate the variable. Here is a simple procedural program which uses the Do loop.
We can do the same thing by using the functional style. When programming in this style we use functions which return values rather then change states of variables. Instead of loops we use "higher functions", that is functions whose arguments are functions. One of such functions is Nest.
There is also a related function NestList
Instead of using the Do loop above we can obtain the same result using the functional approach as follows:
The program runs much faster.
Here f has to be a function of two arguments. Here is an example which shows the working of FoldList:
Finally there is one new and very useful function that appeared in Mathematica 6.
The same result can be achieved using FoldList, however, Accumulate, being a more specialised function, is considerably faster.
This much greater speed of a more specialized function compared with a more general one is typical of Mathematica programming.
http://reference.wolfram.com/mathematica/tutorial/ApplyingFunctionsRepeatedly.html
Block and global variables.
One of the most common uses of Block is to change temporarily the value of a global variable. For example, the global variable $RecursionLimit has by defaul the value:
The reason for this is to stop accidental infinte recurssion from occuring as a result of programming errors. However, this can sometimes be inconvenient. Here is a familiar example.
The value of 256 for $RecursionLimit prevents the code from working. Using Block we can temporarily change this value:
However, note that the global value of $RecursionLimit remains unchanged:
Example 1: Simulating Brownian Motion
One Path
slower alternative
and even slower
Many Paths
A few words about Dynamic and Manipulate
In version 6 of Mathematica, new features appeared which made it possible to use the Front End in a new way. The main idea is that expressions with head Dynamic are updated when their “displayed form” changes. The simplest case is:
Dynamic
Manipulate
Links
