Worksheet 2

We will introduce some new Julia functions. In particular we will see how to use recursions and loops through a small example.

Computing $\sum_{i=1}^{n} i$

First we will warm up your Julia knowledge by showing you how to compute $\sum_{i=1}^{n} i$. There is a well known formula due to Gauss that reads: (more details in https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF)

\begin{equation} \sum_{i=1}^{n} i = \frac{n(n+1)}{2}. \end{equation}

The proof normally needs recursion; however, we will do a proof "by intimidation". We will write a small function that computes the former and test it against the formula, and see that they match even for large $n$.

One extremely easy although suboptimal way of computing $\sum_{i=1}^{n} i$ is to write

This is suboptimal because it needs to allocate the vector $[1:n]$, which is $[1 ,2 ,3 ,4..., n-1, n]$, and then add all the components. This means that we need $\cal{O}(n)$ memory. You can see this problem by running the macro @time, which computes the time and the memory allocation of the function. You can run the snippet below for different $n$ and you should observe that more bytes are being allocated as $n$ increases (the number whoud grow linearly with $n$).

We can perform the sum using a loop only requiring $\cal{O}(1)$ memory.

You can easily test that the two functions provide the same result by running

Now you can see the memory footprint of the new function by running

You can increase $n$ as much as you want and the memory allocated will be independent of $n$. Now that we have a good algorithm to compute $\sum_{i=1}^{n} i$ we will test if the formula is correct by running

Fibonacci numbers

Now that you have warmed up, you will need to compute the Fibonacci sequence (https://en.wikipedia.org/wiki/Fibonacci_number)

\begin{equation} 1,1,2,3,5,8,13,21,... \end{equation}

Now the function below computes the $N$-th term of the Fibonacci sequence

You can see that in order to reduce space and make the code more readable we useda block declaration within the function and within the loop

You can see that in the example above, we declared and assigned a = 1 and b = 2, which is equivalent to

We can use the same syntax to perform different operations such as:

This piece of code assigns the value value of b to a, and the value of a plus b to b. In other words, we are updating the values of a and b.

Now you can check the validity of the fibonacciLoop function by runnin

We can define a recursive function (a function that calls itself)

You can check that both functions provide the same answer

For different implementation of the Fibonacci sequence please see http://www.scriptol.com/programming/fibonacci.php.

Morover, as you know, the Fibonacci sequence is the solution of a finite difference equation given by:

\begin{equation} f_{n+1} = f_{n} + f_{n-1} \end{equation}

with boundary conditions $f_1 = 1$, $f_2 = 1$.

Show that the answer for this equation can be found in closed form. The explicit formula that is given by \begin{equation} f_n = \frac{1}{\sqrt{5}} \left [ \left ( \frac{1+\sqrt{5}}{2} \right )^n - \left ( \frac{1-\sqrt{5}}{2} \right )^n \right]. \end{equation}

This gives a closed formula; however, the formula implies the multiplication by irrational numbers. These irrational numbers can not the excatly expressed using floating point numbers, so we are introducing some errors, and then multiplying those errors together. You can check the errors introduced by running

They provide the same result up to machine precission; however, we can check that the formula approach is much faster, to test how fast they are we will use the macro @time

As you can see, the two functions are almost as fast, (in fact fibonacciFormula lags a bit behind); however, if we try a bigger number

Now you can observe that fibonacciFormula is 5 order of magnitude faster that the recursive Function.

Now we can try to time the iterative function

You can see that the iterative function is extremely fast but it provides a wrong answer. How is that possible?

Answer : The Fibonacci series grows fast, then after a while it gets out of range for int64.

We will modify fibonacciLoop2 slighlty to provide a better answer.

Can you explain the difference? In the first algorithm, all the arithmetic is performed using Int64 numbers. 0 is an Int64 and everything is added is an Int64. In the second version, by defining fibn, fibn_p1 = (0.0,1.0) we are forcing the algorithm to use Float64, that have a much greater range.

Now we can test the difference between Fibonacci using a loop and the formula.

this means that both algorithms provide the same answer up to machine precission.

Computing n!

Now that you have been exposed to the syntax of Julia, write two functions, one iterative and other recursive to compute $n!$

Test your functions using the Julia function factorial

We will write a function, such that if for a number $m$ you will compute the largest integer $n$ such that $n! \leq m$

We can test the function by running

Computing $\int_a^b f(x) dx$

Now we are going to extend what was done in last lab. We can define the function integrateRectangle that will approximate

\begin{equation} \int_a^b f(x) dx \end{equation}

via $\sum_{i = 1}^{N}f(x_i) h$; where $x_i = a + (i-1/2)h$ and $ h = (b-a)/N$

As you can see, a function can receive a function as an argument. Now you can use this function to compute integral numerically using the Rectangle Method https://en.wikipedia.org/wiki/Rectangle_method.