Much to my joy I was able to write a procedure that computes elements of Pascal's triangle, in only a few minutes, directly after spending 5 days trying to understand the exercise before.
It's made easier since it's a recursive call. The way it works is simple. And as a note before I begin, I do remember reading about methods to tackle this problem before, so this isn't something I figured out in a vacuum, but then again I think few things ever are. If you're not familiar with Pascal's triangle, it's a triangle made up of numbers, where each number is the sum of the two numbers above it to the left and right. It starts at 1 and grows basically exponentially.
To start this problem it helps to figure out how to represent the triangle in the computer. We can make life easy by pushing the triangle up against an imaginary left wall so that it'd look like this:
1
11
121
1331
14641
1......
An algorithm for computing values is immediately clear from this. Think in terms of row and column coordinates. The value of any one point is the sum of the point directly above it and the point directly above and to the left. As I was starting to figure at the end of my last post: whenever the row and column coordinates are equal, the value is one. Every first row point, regardless of column, has a value of 1.
Just to recap the pseudo-code-ish-math:
row(0) all = 1
#rows = col# + 1
if col# = row# => 1
if: row# = x, col# = y, & val = $f$(x, y), then $f$(x,y) = $f$(x, y-1) + $f$(x-1, y-1)
So there are three conditions plus one recursive call in this procedure. The recursive call is what makes this procedure work and it's goes thusly:
( + (pascal row (- col 1)) (pascal (- row 1) (- col 1)))
-- which translates to: $f$(x, y-1) + $f$(x-1, y-1)
Now we put that all together to build our procedure:
(define (pascal row col)
(cond ((= row col) 1)
((= row 0) 1)
((> row col) #f)
((+ (pascal row (- col 1)) (pascal (- row 1) (- col 1)) )) ))
))
And it works! I use the Scheme interpreter on repl.it to check the output. Once last note on this procedure: On my first run I forgot to add a breaking function for illegal coordinates. There are no values for points outside Pascal's triangle (I'm sure we can say they're zero, but that's not coded in here), so the procedure will call itself, see that none of the conditions are met, call itself, and repeat, infinitely. So to break out of this loop I wrote the condition that if the row coordinate is larger than the column's, return a value of
False (#f in Scheme).
And that's that.
SICP 1.13
This one I thought I wouldn't do, then did anyway. The book asks you to provide a mathematical proof that Fib(n) (the fibonacci procedure) is the closest integer to $\phi^n/\sqrt5$, where $\phi = (1+\sqrt5)/2$ (golden ratio).
I went ahead with this b/c I thought it'd be important for me to have a better familiarity with mathematical proofs. So I pulled up a post by
BilltheLizard and used that to walk me through the process. He wrote a quick procedure to provide a bit of empirical evidence that I was interested in. I'll get to that in a bit.
So the information we're given is:
$\phi = (1+\sqrt5)/2$
And we're given the hint that:
$\psi = (1 -\sqrt5)/2$
Both these have the property that:
$\phi^2 = \phi+1$ $\phi = 1 + \phi^{-1} $ $1 = \phi-\phi^{-1}$
$\psi^2 = \psi+1$ $\psi = 1 + \psi^{-1} $ $1 = \psi-\psi^{-1}$
This will come in handy when the Algebra comes in. Now to go ahead and break this full proof into parts: there are 3: First we prove that to start, Fib(n) indeed equals $(\phi^n-\psi^n)/\sqrt5$ After that we do what's called the Inductive Step. As I understand it from a Linear Algebra class, mathematical induction is the process of proving something true by showing that: if the thing is true for a base case (let's say 1), and if it is true for an arbitrary case (k), then if it is true for any k + 1 case, it is true for all cases.
We'll do this by proving the defining recurrence relation of the Fibonacci sequence; that is, that any point on the Fibonacci sequence is equal to the sum of the 2 points before it. So we must prove that:
Fib(n+1) = Fib(n) + Fib(n-1)
And this relies on the first proof, because we're going to substitute the math formula for Fib().
Finally, to prove that Fib(n) is the closest integer to $\phi^n/\sqrt5$, we have to prove that the difference between Fib(n) and $\phi^n/\sqrt5$ is always less than $1/2$
So let's get started:
[Step 1]: Prove Fib(n) = $(\phi^n-\psi^n)/\sqrt5$
Compare Fib(n)'s output to $(\phi^n-\psi^n)/\sqrt5$'s output:
Fib(0) = 0
Fib(1) = 1
Fib(2) = Fib(1) + Fib(0) = 1 + 0 = 1
-------------------------------------------
For n = 0:
$(\phi^n - \psi^n)/\sqrt5 = (\phi^0 - \psi^0)/\sqrt5 = (1 - 1)/\sqrt5 = 0$
For n = 1:
$(\phi^n - \psi^n)/\sqrt5 = (\phi^1 - \psi^1)/\sqrt5$
$= ((1+\sqrt5)/2 - ((1-\sqrt5)/2))/\sqrt5 = (1/2+\sqrt5/2 - 1/2 + \sqrt5/2)/\sqrt5$
$= ((2\sqrt5)/2)/\sqrt5 = \sqrt5/\sqrt5 = 1$
For n = 2:
$(\phi^2 - \psi^2)/\sqrt5 = (((1+\sqrt5)/2)^2-((1-\sqrt5)/2)^2)/\sqrt5$
$= (\phi-\psi)/\sqrt5 = \cdot\cdot\cdot = 1$
As an aside, the math checking I had to do so I could substitute in the properties in the last part:
$(1+\sqrt5)/2\cdot(1+\sqrt5)/2 = (1/2+\sqrt5/2)\cdot(1/2+\sqrt5/2)$
$1/4+\sqrt5/4+\sqrt5/4+5/4 = 6/4 + \sqrt5/2$
$= 3/2 + \sqrt5/2 + 1 + (1+\sqrt5)/2$
Now this is all proven and made redundant by remembering the property from before:
$\phi = (1+\sqrt5)/2 \Rightarrow \phi^2 = \phi + 1$ oops...Right..
[Step 2]: Assuming Fib(n) = $(\phi^n-\psi^n)/\sqrt5$, and Fib(n-1) = $(\phi^{n-1}-\psi^{n-1})/\sqrt5$
Prove: Fib(n+1) = $(\phi^{n+1}-\psi^{n+1})/\sqrt5$
Fib(n+1) = Fib(n) + Fib(n-1)
$= (\phi^n-\psi^n)/\sqrt5 + (\phi^{n-1}-\psi^{n-1})/\sqrt5 = (\phi^n-\psi^n+\phi^{n-1}-\psi^{n-1})/\sqrt5$
$= ((\phi^n+\phi^{n-1})-(\psi^n+\psi^{n-1}))/\sqrt5$
$= (\phi^{n+1}(\phi^{-1}+\phi^{-2})-\psi^{n+1}(\psi^{-1}\psi^{-2}))/\sqrt5$
$= (\phi^{n+1}\phi^{-1}(1+\phi^{-1})-\psi^{n+1}\psi^{-1}(1+\psi^{-1}))/\sqrt5$
$= (\phi^{n+1}\phi^{-1}\phi-\psi^{n+1}\psi^{-1}\psi)/\sqrt5$
$= (\phi^{n+1}-\psi^{n+1})/\sqrt5$
Bam.
[Step 3]: Prove Fib(n) is the closest integer to $(\phi^n)/\sqrt5$
Fib(n) = $(\phi^n-\psi^n)/\sqrt5$ = $\phi^{n}/\sqrt5-\psi^{n}/\sqrt5$ $\Rightarrow$ $-\phi^n/\sqrt5 = \psi^{n}/\sqrt5$ $\Leftarrow\Rightarrow$ Fib(n)$-$ $\phi^{n}/\sqrt5 = \psi^{n}/\sqrt5$
$\rightarrow$ We want to prove that the difference between Fib(n) & $\phi^{n}/\sqrt5$ is always $\lt 1/2$
Prove: $\psi^{n}/\sqrt5 \le 1/2$ йа: $\psi^{n} \le \sqrt5/2$
$\psi = (1-\sqrt5)/2 \approx -0.6183....$
$\rightarrow$ since $n$ is an integer & $n \ge 0$, & $ \psi \lt 1$
$\Rightarrow$ We know / Вай хаъ:
$\psi^n \le 1$, for all integers $n \lt 0$
$\rightarrow$ also: $\sqrt5/2 \approx 1.118....$
$\rightarrow$ since $\psi^n \le 1$ & $\sqrt5/2 \gt 1$
$\Rightarrow \psi^n \le \sqrt5/2$
$\Rightarrow$ Fib(n) is the closest integer to $\phi^n/\sqrt5$
QED
QuantumElectroDynamics
ehh, it looked prettier in the notebook atleast
I almost forgot about that procedure..
Now the way BilltheLizard did a preliminary check for Fib(n) was he wrote a procedure that would output values of $\phi^{n}/\sqrt5$:
(define phi
(/ (+ (sqrt 5)) 2)
(define (^ base exponent)
(define (*^ exponent acc)
(if (= exponent 0)
acc
(*^ (exponent 1) (* acc base))))
(*^ exponent 1))
(define (f n)
(/ (^ phi n) (sqrt 5)))
This stumped me for a while but it's actually a very simple procedure. What it does is define exponentiation of the form $X^Y$.
It does this by multiplying a base by itself a number of times specified by its exponent, using an accumulator (acc) to hold incremental values of the exponent. I actually think it's very elegant.
This base exponentiation mechanism essentially works like this:
( *^ exponent accumulator )
( if ( = exponent 0 ) accumulator
else $\rightarrow$ ( *^ ( - exponent 1 ) ( * accumulator base )
so for $2^3$:
$\rightarrow$ (^ 2 3)
$\rightarrow$ (*^ 3 1)
$\rightarrow$ 3 $\neq$ 0 $\Rightarrow$ (*^ (- 3 1) (* 1 2) )
= (*^ 2 2 )
$\rightarrow$ 2 $\neq$ 0 $\Rightarrow$ (*^ (- 2 1) (* 2 2) )
= (*^ (- 1 1) (* 4 2) )
= (*^ 0 8 )
$\rightarrow$ 0 = 0
$\Rightarrow$ return value: accumulator = 8
And that's all there is to it. I wonder how effective this method of learning is, we'll see. Day 10.
