UNB/ CS/ David Bremner/ teaching/ cs2613/ labs/ Lab 19

# Background

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

• GOBG Chapter 2
• GOBG Chapter 4
• GOBG Chapter 5

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

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

# Before the lab

One of the main features of Octave we will discuss is vectorization. To understand it, we need some background material on Linear Algebra. If you've taken a linear algebra course recently, this should be easy, otherwise you will probably need to review

If you don't have time before this lab, make sure you review any needed linear algebra before the next lab.

# Running Octave

• There is a GUI accessible from `Activities -> 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)
>> countourf(peaks)
``````

# Fibonacci

Time
15 minutes
Activity
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/L19/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

endfor
endfunction

%!assert (fib(0) == 0);
%!assert (fib(1) == 1);
%!assert (fib(2) == 1);
%!assert (fib(3) == 2);
%!assert (fib(4) == 3);
%!assert (fib(5) == 5);
```
• We can avoid the need for a temporary variable by calling `deal` function, but it's not clear that would be faster. If you have time, try it.

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

# Fibonaccci as matrix multiplication

Time
20 minutes
Activity
individual

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 easy to implement in octave

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

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

endfunction

%!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

Time
10 minutes
Activity
Demo / discussion

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

• It's possible to compute matrix powers rather quickly (`O(log n)` compared `O(n)`), and since the fast algorithm is also simple, we can hope that octave implements it. Since the source to octave is available, we could actually check this.

• Octave is interpreted, so loops are generally slower than matrix operations (which can be done in a single call to an optimized library). This general strategy is called vectorization, and applies in a variety of languages, usually for numerical computations. In particular most PC hardware supports some kind of hardware vector facility.

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
```

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)
endfunction
```

# Python Quiz

• Questions and unit tests will be distributed via email and teams at or before 9:30.