Learning Mathematica Basics—Functions II

Solve each of the following problems using Mathematica exclusively.

1.	For starters, then, let's define the Fibonnaci recursive function in Mathematica with the commands:

fiba[n_]:=fiba[n-1]+fiba[n-2]
fiba[1]=fiba[2]=1

Note that there is a RETURN at the end of the first line of this command.  Also, we've called the function fiba since we'll be designing another one later called fibb.

2.   OK!  Now let's test out our new function.  Ask for fiba[7].

3.   If you check back to the listing of the Fibonacci sequence in the introduction, you may verify that your answer to problem 2 was correct.  Now let's go a little further out in the sequence.  Find fiba[15], taking careful note of how long Mathematica takes to do the calculation.

4.   Well, how long did it take?  You should have noticed somewhat of a time lag!  Why do you think this happens?  Well, if you consider what is required to find fiba[15] you might start to appreciate the problem.  Finding fiba[15] requires that you find fiba[14] and fiba[13], but they haven't been calculated either yet.  Then to find fiba[14] requires first finding fiba[13]and fiba[12]. . .  Can you see where this is going?  Just to find fiba[15] requires going all the way back to fiba[1], calculating everything in between.  But that's just the beginning.  Finding fiba[14] (as part of finding fiba[15]) requires the same, as does fiba[13]. . .  The bottom line is that recursive functions can require enormous amounts of work and time.  In fact the amount of calculation/time necessary  grows exponentially with how far along the sequence you go.

We're now going to attempt to speed up our Fibonacci function, but in order to determine how well we're doing we need to have something less subjective than just saying "Ooh, that seemed to take longer."  The command we need is called Timing.  Ask Mathematica for its syntax.

5.   Now we're going to use fiba one more time.  Find fiba[20], but wrap the Timing command around the call to fiba[20] so that we can see exactly how long it takes.  Be prepared for quite a wait.

6.   The timing is the first number reported.  The second number, 6765, is the actual answer to the problem.  Timing on my PowerBook was 40 seconds—your computer will probably be different, but that's OK.

Now how can we speed up the Fibonacci function?  Give the command ?fiba in order to find out exactly what Mathematica remembers about fiba.

7.   Notice that all that is remembered is the original definition of fiba.  But we've recently calculated all the way up to fiba[20].  If only Mathematica would remember previous values of the function—ones that it has already calculated—then the speed of calculation of higher values in the sequence should be improved!  The following new function definition has this "memorization" built in.

fibb[n_]:=fibb[n]=fibb[n-1]+fibb[n-2]
fibb[1]=fibb[2]=1

Study the first line carefully—it's actually two equations in one.  The fibb with the wildcard argument (the first one) is just the same as fiba, but the second fibb contains no wildcard.  It's this one that does the "memorizing."  Go ahead and enter this new function.  (Don't worry about any warning messages about spelling.)

8.   Now test fibb by asking for fibb[7].  You should get the same as in problem 2.

9.   Now ask what is known about fibb by issuing ?fibb.

10.   Woah!  It knows all the values up to fibb[7].  (Why not just fibb[7] itself?)

Anyway, now let's test the timing.  We'll do the twentieth term again, so that we can make a direct comparison with problem 5.  Ask for Timing[fibb[20]].

11.   You should have noticed a drastic speed increase over problem 5.  Let's conclude our Fibonacci study by going up to the one-hundredth term of the sequence using fibb—something that would have taken hours using the old fiba.

12.   Now it's your turn.

The not-at-all famous Biff sequence:

                                         4, 12, 20, 28, 36, 44, 52, 60, 68, 76 . . .
                                         
can be thought of as the recursive function:
 
                              biff(n) = 2*biff(n-1) - biff(n-2), biff(1) = 4,  biff(2) = 12
 
 Go ahead and create the function biff in Mathematica using the second (faster) implementation we introduced above.  Use it to calculate biff[10] and biff[20].
 
 (Note:  If you make a mistake when defining a function then it might help to get a fresh start by using the  Clear command.  For example Clear[biff].)