UNB/ CS/ David Bremner/ teaching/ cs2613/ labs/ CS2613 Lab 21


Most of the material here is covered in the Gnu Octave Beginner's Guide, in particular

For some parts, we will refer to the GNU Octave Manual

Running Octave


15 minutes
Demo/Group programming.

Let's dive in to programming in Octave with a straight-forward port of our Python Fibonacci function. Save the following in ~/fcshome/cs2613/labs/L21/fib.m. It turns out to be important that the function name is the same as the file name.

function ret = fib(n)
  a = 0;
  b = 1;
  for i=0:n


%!assert (fib(0) == 0);
%!assert (fib(1) == 1);
%!assert (fib(2) == 1);
%!assert (fib(3) == 2);
%!assert (fib(4) == 3);
%!assert (fib(5) == 5);

Fibnaccci as matrix

20 minutes
Small Groups

The following is a well known identity about the Fibonacci numbers F(i).

[ 1, 1;
  1, 0 ]^n = [ F(n+1), F(n);
               F(n),   F(n-1) ]

Since matrix exponentiation is built-in to octave, this is particularly to impliment in octave

Save the following as ~/fcshome/cs2613/labs/L21/fibmat.m, fill in the two matrix operations needed to complete the algorithm

function ret = fibmat(n)
  A = [1,1; 1,0];


%!assert (fibmat(0) == 0);
%!assert (fibmat(1) == 1);
%!assert (fibmat(2) == 1);
%!assert (fibmat(3) == 2);
%!assert (fibmat(4) == 3);
%!assert (fibmat(5) == 5);
%!assert (fibmat(6) == 8);
%!assert (fibmat(25) == 75025);

Performance comparison

15 minutes
Demo / discussion

We can expect the second Fibonacci implimentation to be faster for two distinct reasons

Of course, the first rule of performance tuning is to carefully test any proposed improvement. The following code gives an extensible way to run simple timing tests, in a manner analogous to the Python timeit method, whose name it borrows.

# Based on an example from the Julia microbenchmark suite.

function timeit(func, argument, reps)
    times = zeros(reps, 1);

    for i=1:reps
      tic(); func(argument); times(i) = toc();

    times = sort(times);
    fprintf ('%s\tmedian=%.3fms mean=%.3fms total=%.3fms\n',func2str(func), median(times)*1000,
             mean(times)*1000, sum(times)*1000);

What are the new features of octave used in this sample code?

We can either use timeit from the octave command line, or build a little utility function like

function bench
  timeit(@fib, 42, 100000)
  timeit(@fibmat, 42, 100000)

Measuring CPU time

25 minutes
Small groups

Our timeit function measures Wall clock time. This means in particular that it is susceptible to interference from other activities on the same computer.

Using the profiler

25 minutes
Small groups

Total time, as provided by timeit and ctimeit is useful for comparing two complete functions, it doesn't tell you where the time is being used within a given function. Octave supports profiling to help locate hotspots within your code.