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.

5. More Advanced Topics_1.gif

5. More Advanced Topics_2.gif

5. More Advanced Topics_3.gif

5. More Advanced Topics_4.gif

Let's compare the following two definitions of the Fibonacci numbers. First we start with a usual recursive definition.

5. More Advanced Topics_5.gif

5. More Advanced Topics_6.gif

5. More Advanced Topics_7.gif

5. More Advanced Topics_8.gif

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 = .

5. More Advanced Topics_9.gif

5. More Advanced Topics_10.gif

5. More Advanced Topics_11.gif

5. More Advanced Topics_12.gif

5. More Advanced Topics_13.gif

Computing even the 50th Fibonacci number takes virtually no time.

We can see the difference between the two definitions by using the function Trace:

5. More Advanced Topics_14.gif

5. More Advanced Topics_15.gif

5. More Advanced Topics_16.gif

5. More Advanced Topics_17.gif

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

5. More Advanced Topics_18.gif

Global`Fib1

Fib1[0]=0
 
Fib1[1]=1
 
Fib1[n_]:=Fib1[n-1]+Fib1[n-2]

5. More Advanced Topics_19.gif

5. More Advanced Topics_20.gif

5. More Advanced Topics_21.gif

Global`Fib2

Fib2[0]=0
 
Fib2[1]=1
 
Fib2[2]=1
 
Fib2[3]=2
 
Fib2[4]=3
 
Fib2[5]=5
 
Fib2[n_]:=Fib2[n]=Fib2[n-1]+Fib2[n-2]

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

5. More Advanced Topics_22.gif

5. More Advanced Topics_23.gif

5. More Advanced Topics_24.gif

5. More Advanced Topics_25.gif

5. More Advanced Topics_26.gif

5. More Advanced Topics_27.gif

5. More Advanced Topics_28.gif

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:

5. More Advanced Topics_29.gif

5. More Advanced Topics_30.gif

5. More Advanced Topics_31.gif

5. More Advanced Topics_32.gif

This can be also written as

5. More Advanced Topics_33.gif

5. More Advanced Topics_34.gif

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.

5. More Advanced Topics_35.gif

5. More Advanced Topics_36.gif

5. More Advanced Topics_37.gif

5. More Advanced Topics_38.gif

5. More Advanced Topics_39.gif

5. More Advanced Topics_40.gif

5. More Advanced Topics_41.gif

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.

5. More Advanced Topics_42.gif

5. More Advanced Topics_43.gif

5. More Advanced Topics_44.gif

5. More Advanced Topics_45.gif

5. More Advanced Topics_46.gif

5. More Advanced Topics_47.gif

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

5. More Advanced Topics_48.gif

5. More Advanced Topics_49.gif

5. More Advanced Topics_50.gif

5. More Advanced Topics_51.gif

5. More Advanced Topics_52.gif

5. More Advanced Topics_53.gif

5. More Advanced Topics_54.gif

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.

5. More Advanced Topics_55.gif

5. More Advanced Topics_56.gif

5. More Advanced Topics_57.gif

5. More Advanced Topics_58.gif

5. More Advanced Topics_59.gif

5. More Advanced Topics_60.gif

5. More Advanced Topics_61.gif

5. More Advanced Topics_62.gif

5. More Advanced Topics_63.gif

5. More Advanced Topics_64.gif

5. More Advanced Topics_65.gif

5. More Advanced Topics_66.gif

5. More Advanced Topics_67.gif

5. More Advanced Topics_68.gif

5. More Advanced Topics_69.gif

5. More Advanced Topics_70.gif

5. More Advanced Topics_71.gif


Another important example:

5. More Advanced Topics_72.gif

5. More Advanced Topics_73.gif

5. More Advanced Topics_74.gif

5. More Advanced Topics_75.gif

5. More Advanced Topics_76.gif

Although foo was definied outside Block, its value inside Block is changed. This does not happen when we use Module:

5. More Advanced Topics_77.gif

5. More Advanced Topics_78.gif

5. More Advanced Topics_79.gif

5. More Advanced Topics_80.gif

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.

5. More Advanced Topics_81.gif

5. More Advanced Topics_82.gif

5. More Advanced Topics_83.gif

5. More Advanced Topics_84.gif

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.

5. More Advanced Topics_85.gif

5. More Advanced Topics_86.gif

5. More Advanced Topics_87.gif

5. More Advanced Topics_88.gif


There is also a related function NestList

5. More Advanced Topics_89.gif

5. More Advanced Topics_90.gif

5. More Advanced Topics_91.gif

5. More Advanced Topics_92.gif

Instead of using the Do loop above we can obtain the same result using the functional approach as follows:

5. More Advanced Topics_93.gif

5. More Advanced Topics_94.gif

The program runs much faster.

5. More Advanced Topics_95.gif

5. More Advanced Topics_96.gif

Here f has to be a function of two arguments. Here is an example which shows the working of FoldList:

5. More Advanced Topics_97.gif

5. More Advanced Topics_98.gif

5. More Advanced Topics_99.gif

5. More Advanced Topics_100.gif


Finally there is one new and very useful function that appeared in Mathematica 6.

5. More Advanced Topics_101.gif

5. More Advanced Topics_102.gif

5. More Advanced Topics_103.gif

5. More Advanced Topics_104.gif

The same result can be achieved using FoldList, however, Accumulate, being a more specialised function, is considerably faster.

5. More Advanced Topics_105.gif

5. More Advanced Topics_106.gif

 

5. More Advanced Topics_107.gif

5. More Advanced Topics_108.gif

5. More Advanced Topics_109.gif

5. More Advanced Topics_110.gif

5. More Advanced Topics_111.gif

5. More Advanced Topics_112.gif

5. More Advanced Topics_113.gif

5. More Advanced Topics_114.gif

5. More Advanced Topics_115.gif


This much greater speed of a more specialized function compared with a more general one is typical of Mathematica programming.

 

 

 

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:

5. More Advanced Topics_116.gif

5. More Advanced Topics_117.gif

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.

5. More Advanced Topics_118.gif

5. More Advanced Topics_119.gif

5. More Advanced Topics_120.gif

5. More Advanced Topics_121.gif

The value of 256 for $RecursionLimit prevents the code from working. Using Block we can temporarily change this value:

5. More Advanced Topics_122.gif

5. More Advanced Topics_123.gif

5. More Advanced Topics_124.gif

5. More Advanced Topics_125.gif

However, note that the global value of $RecursionLimit remains unchanged:

5. More Advanced Topics_126.gif

5. More Advanced Topics_127.gif

Example 1: Simulating Brownian Motion

One Path

5. More Advanced Topics_128.gif

slower alternative

5. More Advanced Topics_129.gif

and even slower

5. More Advanced Topics_130.gif

5. More Advanced Topics_131.gif

5. More Advanced Topics_132.gif

5. More Advanced Topics_133.gif

5. More Advanced Topics_134.gif

Many Paths

5. More Advanced Topics_135.gif

5. More Advanced Topics_136.gif

5. More Advanced Topics_137.gif

5. More Advanced Topics_138.gif

5. More Advanced Topics_139.gif

5. More Advanced Topics_140.gif

5. More Advanced Topics_141.gif

5. More Advanced Topics_142.gif

5. More Advanced Topics_143.gif

5. More Advanced Topics_144.gif

5. More Advanced Topics_145.gif


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

5. More Advanced Topics_146.gif

5. More Advanced Topics_147.gif

5. More Advanced Topics_148.gif

5. More Advanced Topics_149.gif

5. More Advanced Topics_150.gif

5. More Advanced Topics_151.gif

5. More Advanced Topics_152.gif

5. More Advanced Topics_153.gif

5. More Advanced Topics_154.gif

5. More Advanced Topics_155.gif

5. More Advanced Topics_156.gif

5. More Advanced Topics_157.gif

5. More Advanced Topics_158.gif

5. More Advanced Topics_159.gif

5. More Advanced Topics_160.gif

5. More Advanced Topics_161.gif

5. More Advanced Topics_162.gif

5. More Advanced Topics_163.gif

5. More Advanced Topics_164.gif

5. More Advanced Topics_165.gif

5. More Advanced Topics_166.gif

5. More Advanced Topics_167.gif

5. More Advanced Topics_168.gif

5. More Advanced Topics_169.gif

5. More Advanced Topics_170.gif

5. More Advanced Topics_171.gif


Manipulate

5. More Advanced Topics_172.gif

5. More Advanced Topics_173.gif

5. More Advanced Topics_174.gif

5. More Advanced Topics_175.gif

5. More Advanced Topics_176.gif

5. More Advanced Topics_177.gif

5. More Advanced Topics_178.gif

5. More Advanced Topics_179.gif

5. More Advanced Topics_180.gif

5. More Advanced Topics_181.gif

5. More Advanced Topics_182.gif

5. More Advanced Topics_183.gif

5. More Advanced Topics_184.gif

5. More Advanced Topics_185.gif

5. More Advanced Topics_186.gif

5. More Advanced Topics_187.gif

5. More Advanced Topics_188.gif

5. More Advanced Topics_189.gif

5. More Advanced Topics_190.gif

5. More Advanced Topics_191.gif

5. More Advanced Topics_192.gif

Links

5. More Advanced Topics_193.gif

5. More Advanced Topics_194.gif