# 8 - Recursion (2), Euclid's algorithm

## How many ways are there to write n as the sum of twos and ones

$F_n =$ # of ways to write $n$ as the sum of ones and twos

$\{nothing\}=0$ 1 way to count 0 with ones and twos

For $n \geq 2$ we can either
- Start with a 1
- $1 + x = n$ We need to find x
- x is a string of ones and twos that adds up to $n-1$
- Start with a 1 followed by any sum of ones and twos that add up to $n$ ($F_{n-1}$)
- Start with a 2
- $2 + x = n$
- 2 + anything that adds up to $n-2$
- $F_{n-2}$

This is pretty much the same as the fibonacci sequence and the two sets of strings that start with a one and strings that start with a two are disjoint.

So

$F_n = F_{n-1} + F_{n-2}$
$f = fibonacci function$
$F_n = f_{n+1}$

## Greatest common divisor (Euclid's algorithm)
Finds the greatest common divisor of two integers $a > b \geq 1$
The largest integer $d$ that divides $a$ and $b$
Ex: $GCD(20,15)=5$
$20 / 5 = 4, 15 / 5 =3$

Uses the modulus operator (remainder after integer division)
- For any positive integers $a$ and $b$
- $a = q \times b + r$ where $q$ is an integer
- $r \in \{0,1,...,b-1\}$

Ex:
$a = 20, b=6$
$a = 3 \times b + 2$
$a \mod b = r$

Ex2:
$17 \mod 12 = 5$
$17 = (1 \times 12) + 5$

Ex3:
$23 \mod 1 = 0$
$23 = (23 \times 1) + 0$

Ex4:
$45 \mod 15 = 0$
$45 = (3 \times 15) + 0$

- If $a \mod b = 0$ then $GCD(a,b) = b$
- $a = q \times b + 0$
- $\frac{a}{b} = q, \frac{b}{b} = 1$

Lemma: If $a \mod b = r \neq 0$ then:
- $GCD(a,b) = GCD(b,r)$

Proof: Let $d$ be any common divisor of $a$ and $b$
This means that
- $\frac{a}{d}$ and $\frac{b}{d}$ are integers
- $a = q \times b + r$ (a is equal to some multiple times b plus whatever the remainder after division is)
- $r = a\mod b$
- 
- Every common divisor of $a$ and $b$ is also a divisor of $r$

Euclid(a,b) //requires a > b >= 1
    r = a mod b
    if r = 0 return b
    return Euclid(b, r)

This doesn't run forever because $r \in \{0,...,b-1\}$ $r < b < a$
The arguments keep getting smaller and none of them are equal to 0. Eventually one will be equal to 1.


All of the divisors of a and b are also common divisors of b and r. in particular then, the greatest common divisor of a and b is the greatest common divisor of b and r. the gcd of b and r can't be bigger than the gcd of a and b because it will be smaller than b which is smaller than a.

This algorithm is used very commonly in cryptography but it's being used on number that are represented with 10000 bits.

---

- Let $M(u,d)=$ the number of mod operations performed by Euclid(a,b)
$M(34,21) = 7$
$M(75,45) = 3$

**Claim:**
Let $a > b \geq 1$ and let $m = M(a,b)$
Then $a \geq f_{m+2}$ and $b \geq f_{m+1}$ $f = fibonacci\ number$

**Proof: by induction on $m$**
Base case: $m=1$
Then that mst mean that $a > b \geq 1, a \geq 2$
$b \geq f_{1+1} = f_{2} = 1$
$a \geq f_{1+2} = f_3 = 2$

Now assume that this is true for all $k \in \{1,...,m-1\}$. Proove for $m \geq 2$

$gcd(a,b) = gcd(b,r)$
$m = M(a,b) = 1 + M(b,r)$

We know that we must make at least one recursive call, and the number of mod operations after the first recursive call will be 1 less than the number of mod operations for a and b. After making the first recursive call, b is now the first argument. with the inductive hypothesis, this means that $b \geq f_{m-1+2} = f_{m+1}$ which follows.

We still haven't proved anything for a

we know that $a = q\times b + r$
we know $a > b$, this means that $\frac{a}{b} > 1$ and $q \geq 1$
so $a = q\times b + r \geq b+r \geq f_{m+1} + f_{m} = f_{m+2}$


---
if $a \geq f_{m+2}$ then $a \geq \frac{\phi^m + 2}{\sqrt{5}} + 1$
- $a - 1 \geq \frac{\phi^m + 2}{\sqrt{5}}$
- $\sqrt{5}(a-q) = \phi^m + 2$
- $log(\sqrt{5}(a-1)) = m + 2 log\phi$
- $m \leq \frac{log(a-1)}{log\phi} + \frac{log\sqrt{5}}{log\phi} - 2$
- 
- running time of algorithm is proportional to the logarithm of $a$
###### tags: `COMP2804`, `Recursion`