# 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

## Running Octave

There is a GUI accessible from

`Activities -> GNU Octave`

, or by running from the command line`>> octave`

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

`>> octave --no-gui`

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/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
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 write this more consisely using the
`deal`

function, but we leave that for later. 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 arround the logical test.

# Fibnaccci as matrix

- Time
- 20 minutes
- Activity
- 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];
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
- 15 minutes
- Activity
- Demo / discussion

We can expect the second Fibonacci implimentation 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 impliments 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?

`tic`

,`toc`

, from GOBG8, GO 36.1- Function Handles
- what else?

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

# Measuring CPU time

- Time
- 25 minutes
- Activity
- 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.

Use the octave builtin

`cputime`

to write a function ctimeit that measures the cpu time taken by a function.`>> ctimeit( @fibmat, 42, 100000) fibmat mean = 0.018ms total = 1.812s`

Note that the

`cputime`

is not as precise as`toc`

, you will need to change the way time is measured. There's a reason median is not reported here.What inaccuracy/overhead is built in to this method?

# Using the profiler

- Time
- 25 minutes
- Activity
- 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.

Use the profiler to measure a single call to

`fib(1000)`

and`fibmat(1000)`

. Don't forget to clear the profiling information between experiments. What do you observe about the precision of reported times? What other (more useful) information can you get from the profile?Repeat the experiment with a larger number of repeats of each function call. Compare the results with

`timeit`

and`ctimeit`

for the same number of repetitions. There is at least one mysterious (large) difference. What do think might explain it?