Background

We will mainly rely on the Octave Interpreter Reference. A more tutorial style guide is the Gnu Octave Beginner's Guide, which is available in ebook form from the UNB library.

We'll refer to the online text by Robert Beezer for linear algebra background. We can happily ignore the stuff about complex numbers.

Python Quiz

The first half of the lab will be a quiz on python

Running Octave

• There is a GUI accessible from Applications -> FCS -> GNU Octave, or by running from the command line

    % octave --gui
  

• There is also a REPL accessible from the command line by running

    %  octave
  

• To sanity check your octave setup, run the following plots

    >> surf(peaks)
    >> contourf(peaks)
  

Recursive Fibonacci

Here is a JavaScript recursive function for Fibonacci:

function fib(n) {
    if (n<=0)
        return 0;
    if (n<=2)
        return 1;
    else
        return fib(n-1)+fib(n-2);
}

Let's translate this line by line into an Octave function.

Save the following in ~/cs2613/labs/L20/recfib.m; the name of the file must match the name of the function.

function ret = recfib(n)
  if (n <= 0)
    ret = 0;
  elseif (n <= 2)
    ret = 1;
  else
    ret = recfib(n-1) + recfib(n-2);
  endif
endfunction

Like the other programming languages we covered this term, there is a built in unit-test facility that we will use. Add the following to your function

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

• Note the %! assert. These are unit tests that can be run with

    >> test fib
  

• The syntax for %!assert is a bit fussy, in particular the parentheses are needed around the logical test.

Questions for your journal

• How are values returned from functions in octave?

Table based Fibonacci

A powerful technique for making recursive A more problem specific approach (sometimes called dynamic programming) is to fill in values in a table.

Save the following in ~/cs2613/labs/L20/tabfib.m. Complete the missing line by comparing with the recursive version, and thinking about the array indexing.

function ret = tabfib(n)
  table = [0,1];
  for i = 3:(n+1)
    table(i)=
  endfor
  ret = table(n+1);
endfunction

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

Questions for your journal

• What are two important differences about array access in Octave compared to Python and JavaScript?

Performance comparison

Let's measure how much of a speedup we get by using a table.

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();
    end

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

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

function bench
  timeit(@recfib, 25, 10)
  timeit(@tabfib, 25, 10)
endfunction

Questions for your journal

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

• Roughly how much speedup is there for using tables to compute the 25th fibonacci number?

Before next lab