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.
No comments:
Post a Comment