Content from 2008-02

SICP Section 1.2
posted on 2008-02-29 19:39:36

I finally finished SICP Section 1.2 last night. I'm tremendously excited because this means that next week I can start tackling Higher Order Functions and (I hope) Closures. At any rate, here is the last month's work:



Resources:

Read: Chapter 1 through Section 1.2

Watch: Lectures 1-b

Checked against: Eli Bendersky's Blog, SICP Wiki, Ken Dyck's Solutions, Autodidact and Lispy for Inspiration.


SICP Notes and Exercises:


Notes

Pg. 35: Explanations of Iteration and Recursion in Processes and Procedures and Tail-Recursion in Compilers.


Maybe I was wrong about SICP. I mean the hardest thing about these exercises was letting the stuff sit in my head for a bit. And the motivation to get some of the more lengthy ones done. We'll see how this goes.


Quotes

"A recursive definition does not necessarily lead to a recursive process." - Gerald Jay Sussman, SICP Lecture 1-B's Time-Space Complexity explanation, approx. 25:30 - 30:30


"The key to understanding complicated things is knowing what not to look at." - Gerald Jay Sussman, SICP Lecture 1-B from Swiss Archive, approx. 10:00


"The reason why people think of programming as being hard is because you're writing down a general rule which is going to be used for lots of instances that a particular instance must process correctly." - Gerald Jay Sussman, SICP Lecture 1-B from Swiss Archive, approx. 46:45


Exercises

1.9:

The first procedure evaluates as follows:



(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

This is a recursive procedure and a recursive process.


The second procedure evaluates as follows:



(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

This is a recursive procedure but an iterative process.


1.10:

(A 1 10) evaluates as follows:



(A 0 (A 1 9))
(A 0 (A 0 (A 1 8)))
(A 0 (A 0 (A 0 (A 1 7))))
(A 0 (A 0 (A 0 (A 0 (A 1 6)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
(A 0 (A 0 (A 0 (A 0 (A 0 32)))))
(A 0 (A 0 (A 0 (A 0 64))))
(A 0 (A 0 (A 0 128)))
(A 0 (A 0 256))
(A 0 512)
1024

(A 2 4) evaluates as follows:



(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 4))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
(A 1 (A 0 (A 0 (A 0 (A 1 1)))))
(A 1 (A 0 (A 0 (A 0 2))))
(A 1 (A 0 (A 0 4)))
(A 1 (A 0 8))
(A 1 16)
(A 0 (A 1 15))
(A 0 (A 0 (A 1 14)))
(A 0 (A 0 (A 0 (A 1 13))))
(A 0 (A 0 (A 0 (A 0 (A 1 12)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 11))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 10)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 9))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 8)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 7))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 6)))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32)))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 64))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 128)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 256))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 512)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1024))))))
(A 0 (A 0 (A 0 (A 0 (A 0 2048)))))
(A 0 (A 0 (A 0 (A 0 4096))))
(A 0 (A 0 (A 0 8192)))
(A 0 (A 0 16384))
(A 0 32768)
65536

(A 3 3) evaluates as follows:



(A 2 (A 3 2))
(A 2 (A 2 (A 3 1)))
(A 2 (A 2 2))
(A 2 (A 1 (A 2 1)))
(A 2 (A 1 2))
(A 2 (A 0 (A 1 1)))
(A 2 (A 0 2))
(A 2 4)
65536

(see evaluation of (A 2 4) above)


The defined procedures f, g, and h intriguingly map as follows:

(f n) -> (* 2 n)

(g n) -> 2^n

(h n) -> 2 raised to itself, n times.


##NOTE:

In the book examples are given of recursive and iterative ways to compute the fibonacci sequence. However, the example given for the fibonacci sequence computes a term beyond what is desired to arrive at it's final answer. The termination condition is count = 0 at which point b is returned. This is a small change to that program to fix what I perceive as a flaw. Have I missed something?

My version returns a when count = 1.



(define (fib n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 1)
a
(fib-iter (+ a b) a (- count 1))))

1.11:

A tree recursive process that computes f is demonstrated in the following procedure:



(define (f n)
(cond ((< n 3) n)
((or (= n 3) (> n 3))
(+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3)))))))

An iterative process that computes f is demonstrated in the following procedure:



(define (f n)
(f-iter 2 1 0 n))

(define (f-iter a b c count)
(cond ((< count 3) count)
(else (f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))

Figuring out the iterative process was scary. It was the first moment I thought I wouldn't be able to do this and might need real help. I was unsure of whether I needed three or four state variables. It clicked after a few minutes of thinking though and was much smoother from there.


1.12:

This one actually gave me some trouble for a bit because I wanted to solve the problem in a non-standard way. After a while, I cracked and read the precursor text (but not the code) to Eli Bendersky's solution and noticing that he defined the function with two arguments (for columns and rows) arrived fairly quickly with that insight at what seems to be the more or less standard solution. I had this much completed for a week or more but got stalled trying to figure out the problem of a pascal function that takes one argument. That diversion contributed greatly to the delay in my progress. I did solve it though and posted the results separately. Here's the standard solution:



(define (pas row col)
(cond ((= row 1) 1)
((= col 1) 1)
((= row col) 1)
(else (+ (pas (- row 1) (- col 1))
(pas (- row 1) col)))))
;Value: pas

1.13:

I need to define a few things for this one first.

rad = the square root of 5 or


(sqrt 5)

phi = (1 + rad) / 2 or


(/ (+ 1 rad) 2)

psi = (1 - rad) / 2 or


(/ (- 1 rad) 2)

fib = you remember our fibonacci function from before right? That's all this is.


Prove that Fib(n) is the closest integer to (/ (phi ^ n) rad). Hint: Use psi as defined above, induction and the definition of the Fibonacci numbers to prove that Fib(n) = ((phi ^ n) - (psi ^ n)) / rad.


Okay, this one is intimidating for a number of reasons. One being that I've never done a formal proof before. At least that I can remember. I've seen proofs done and I've read one or two but I've never done one. Either my math education was lax or I was lax about my math education. In fairness, it was probably a bit of both. That unfamiliarity combined with the aforementioned pascal with a single argument problem served to keep me unmotivated and distracted for a bit.


Prove: That Fib(n) = ((phi ^ n) - (psi ^ n)) / rad.

First, you have to prove your base cases.


Fib (0) = ((phi ^ 0) - (psi ^ 0)) / rad.

That reduces to, 0 = (1 - 1) / rad, So the first base case holds.


Fib (1) = ((phi ^ 1) - (psi ^ 1)) / rad.

That reduces to, 1 = ((1 / 2) + (rad / 2) - (1 / 2) + (rad / 2)) / rad.

That reduces to, 1 = rad / rad, so the second base case holds.


The definition of Fibonacci numbers is that fib(n) = fib(n-1) + fib(n-2) so fib(2) = 0 + 1 = 1. Having found that our lemma is true for n-1 and n-2 will it hold for n?


Fib (2) = ((phi ^ 2) - (psi ^ 2)) / rad.

Remembering that Phi is the golden ratio it meets the condition that (phi ^ 2) = phi + 1.

This gives fib (2) = (2.61803398 - 0.38196601) / rad.

This reduces to fib (2) = 2.23606797 / rad giving 1.


Thus, our lemma holds for fib(n). This does not explain how Fib(n) is always the closest integer to phi ^ n / rad though.


To explain that we must note that in the base case of 1 it holds as phi ^ n / rad evaluates to 0.723606798 and Fib(1) is 1. So, it holds here.

We may then observe that psi being less than 1 will always approach zero as it's exponent is increased.

Thus, the difference between the fib(n) and (/ (phi ^ n) rad) will always be less than 0.381 for n >= 2.

This is what we needed to show.


Whew. After checking this against other people's solutions it turns out I'm not crazy and am roughly correct in my proof which is a relief.


1.14:

Okay. I drew the tree on paper but trying to draw this tree in ASCII for you guys would about kill me. Thankfully on checking my solution I was lucky to find a correct tree image which I will steal with credit. Thanks, Bhrgunatha.

Here is the tree.


As for the order, we can observe that at least in terms number of steps the growth follows that of our tree-recursive fibonacci function and is exponential. I think it's growing at O(xn) but it could be growing at O(nx). Has anyone come to a definitive conclusion about this? Upon checking Ken Dyck's site again I see that Tim Eichner has an interesting solution. Can anyone confirm this?


1.15:

a. How many times is the procedure p applied when (sine 12.15) is evaluated?



(p (sine 4.05))
(p (p (sine 1.35)))
(p (p (p (sine 0.45))))
(p (p (p (p (sine 0.15)))))
(p (p (p (p (p (sine 0.05))))))
(p (p (p (p (p 0.05)))))

P is applied 5 times.


b. What is the order of growth in space and number of steps (as a function of a) used by the process generated by the sine procedure when (sine a) is evaluated?


This one I did need help with. I realized quite clearly that the growth was related to the number of divisions by 3 our angle took to get below the threshold (0.01). I did not realize that the abstraction I was looking for to describe this growth was that of a logarithm. That being said, I checked a few other solutions and went over the wiki page for logarithms once or twice. I really need to order Spivak's Calculus now. Anyway, the process is O(log(a)) in both space and time. Specifically it's O(log3(n)).


1.16:

This was tricky until I modeled the state transformations holding to the rule suggested for (* a (b^n)). Once I did that it was pretty easy.



(define (expt b n)
(define (expt-iter b n a)
(cond ((= n 0) a)
((even? n) (expt-iter (square b) (/ n 2) a))
(else (expt-iter b (- n 1) (* a b)))))
(expt b n 1))
;Value: expt-iter

(expt-iter 2 1000 1)
1071508607186267320948425049060001810561404811705533607443750388370351051124936122493198378815695858127594672917553146825187
1452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062
914571196477686542167660429831652624386837205668069376
;;That's a 300 digit number. This algorithm is O(log n). This computed in 16 steps.

1.17:



(define (* a b)
(define (double x)
(+ x x))
(define (halve x)
(/ x 2))
(cond ((= b 0) 0)
((= a 0) 0)
((= b 1) a)
((even? b) (* (double a) (halve b)))
(else (+ a (* a (- b 1))))))
;Value: *

(* 2 1000)
;Value: 2000
;;16 steps again. logarithmic in time. space too? I think it's just linear in space.

1.18:



(define (* a b)
(define (double x)
(+ x x))
(define (halve x)
(/ x 2))
(define (*-iter a b c)
(cond ((= b 0) 0)
((= a 0) 0)
((= b 1) (+ a c))
((even? b) (*-iter (double a) (halve b) c))
(else (*-iter a (- b 1) (+ c a)))))
(*-iter a b 0))
;Value: *

(* 2 1000)
;Value: 2000
;;16 steps again. logarithmic and iterative, so it does it in O(1) space. boo-yah. today was a good day to code.

1.19:

This was just a really difficult problem to understand. I wasn't even sure what they were really asking. Once I realized I just needed to use algebra to try and expand and then factor out a few things I felt a lot more comfortable.



(define (fib n)
(fib-iter 1 0 0 1 n))
;Value: fib

(define (fib-iter a b p q count)
(cond ((= count 0 ) b)
((even? count)
(fib-iter a
b
(+ (square p) (square q)) ;; compute p'
(+ (* 2 p q) (square q)) ;; compute q'
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))
;Value: fib-iter

1.20:

This is one of those exercises that Abelman and Sussman are sort of bastards for including.


;;Normal order evaluation is fully expand to primitives and then reduce.

;;Applicative-order is...well, what we've been doing all along.


How many remainder operations are performed in the normal order version of

(gcd 206 40)?


How many in the applicative order version?

4: (206 4), (40 6), (6 4), (4 2)


Applicative order first:

(gcd 206 40)

(gcd 40 (remainder 206 40))

(gcd 40 6)

(gcd 6 (remainder 40 6))

(gcd 6 4)

(gcd 4 (remainder 6 4))

(gcd 4 2)

(gcd 2 (remainder 4 2))

(gcd 2 0)

2


Normal order version:

(gcd 206 40)

;;we can count the number of times remainders occur in b, which is always evaluated.

(gcd 40 (remainder 206 40)) ;;rc = 1

if (= (remainder 206 40) 0) = false


(gcd (remainder 206 40) (remainder 40 (remainder 206 40)))) ;;rc = 1+2

if (= (remainder 40 6) 0) = false


(gcd (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) ;;rc = 1+2+4

if (= (remainder 6 4) 0) = false


(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))) ;;rc = 1+2+4+7

if (= (remainder 4 2) 0) = true!

now that if is true we evaluate a: (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) which has 4 remainders to the 14 that have been evaluated in prior predicates. tada! 18 evaluations in total for normal order. 4, if you didn't notice, for applicative order.


GCD is effectively a loop here and the only way for the loop to exit is for the if predicate to evaluate to true, after which the consequent is evaluated. The alternate is only substituted for in this case, never evaluated outright as it never becomes primitive.


In this way, the problem seems to me more of a study into the if conditional than evaluation models. Once you understand that the alternate never gets evaluated, you can simply figure out how many remainders get fed to it before it's true and then how many are in the consequent.


That's the best I could come up with for this one but Eli Bendersky has a solution you may find more clear or detailed.


1.21:



(smallest-divisor 199)
;Value: 199

(smallest-divisor 1999)
;Value: 1999

(smallest-divisor 19999)
;Value: 7

1.22:

The code for this exercise is not particularly difficult. It's not easy but it's fairly straightforward. Because this exercise was written over 10 years ago though it's pretty difficult to use on modern hardware. You're supposed to observe algorithmic efficiency because this code is supposed to stress your hardware. Unfortunately, in 2008 this code makes my hardware yawn for numbers on the scale they were asking for. So I started things off at 13 digits and scaled up from there. I also decided to rework the code so that it only outputs when it finds a prime.



(define (start-prime-test n start-time)
(if (prime? n)
(report-prime (- (runtime) start-time) n)))

(define (report-prime elapsed-time n)
(newline)
(display n)
(display " *** ")
(display elapsed-time))

(define (search-for-primes current end)
(cond ((even? current) (search-for-primes (+ current 1) end))
((> current end) (display " done! "))
(else (timed-prime-test current)
(search-for-primes (+ current 2) end))))

So, there's the code. Now for my results:

(search-for-primes 100000000000 100000000060)


100000000003 *** 1.1600000000000037

100000000019 *** 1.1899999999999977

100000000057 *** 1.240000000000009 done!

;Unspecified return value


(search-for-primes 1000000000000 1000000000070)


1000000000039 *** 3.91

1000000000061 *** 3.759999999999998

1000000000063 *** 3.9400000000000013 done!

;Unspecified return value


(search-for-primes 10000000000000 10000000000100)


10000000000037 *** 12.280000000000001

10000000000051 *** 12.510000000000005

10000000000099 *** 12.200000000000003 done!

;Unspecified return value


(search-for-primes 100000000000000 100000000000098)


100000000000031 *** 38.190000000000026

100000000000067 *** 38.16

100000000000097 *** 37.95000000000002 done!

;Unspecified return value


Checking all of these it appears we are very close to the projected (sqrt 10) increase per digit.


1.23:



(define (find-divisor n test-divisor)
(cond ((> (square n) n) n)
((= (modulo n test-divisor) 0) test-divisor)
(else (find-divisor n (next test-divisor)))))
;Value: find-divisor

(define (next n)
(cond ((even? n) (+ n 1))
(else (+ n 2))))
;Value: next

The results this time were:

(search-for-primes 100000000000 100000000060)


100000000003 *** .7400000000000091

100000000019 *** .7200000000000273

100000000057 *** .7099999999999795 done!

;Unspecified return value


(search-for-primes 1000000000000 1000000000070)


1000000000039 *** 2.3600000000000136

1000000000061 *** 2.2900000000000205

1000000000063 *** 2.319999999999993 done!

;Unspecified return value


(search-for-primes 10000000000000 10000000000100)


10000000000037 *** 7.350000000000023

10000000000051 *** 7.340000000000032

10000000000099 *** 7.189999999999998 done!

;Unspecified return value


(search-for-primes 100000000000000 100000000000098)


100000000000031 *** 23.110000000000014

100000000000067 *** 22.879999999999995

100000000000097 *** 22.920000000000016 done!

;Unspecified return value


This time we also are pretty close to half the previous times but it's slightly over half.


1.24:



(define (start-prime-test n start-time)
(if (fast-prime? n 500)
(report-prime (- (runtime) start-time) n)))
;Value: start-prime-test

And these results were:

(search-for-primes 100000000000 100000000060)


100000000003 *** 9.999999999990905e-3

100000000019 *** 0.

100000000057 *** 9.999999999990905e-3 done!

;Unspecified return value


(search-for-primes 1000000000000 1000000000070)


1000000000039 *** 0.

1000000000061 *** 9.999999999990905e-3

1000000000063 *** 0. done!

;Unspecified return value


(search-for-primes 10000000000000 10000000000100)


10000000000037 *** 0.

10000000000051 *** 0.

10000000000099 *** 0. done!

;Unspecified return value


(search-for-primes 100000000000000 100000000000098)


100000000000031 *** 9.999999999990905e-3

100000000000067 *** 0.

100000000000097 *** 0. done!

;Unspecified return value


We can see that this is definitely in O(log(n)). The times have gone below the precision of my instruments in most cases.


1.25:

I honestly had to look to Eli and Ken for help on this one. I was hand evaluating the original code before trying Alyssa's and having some trouble. I had noticed that the fast-expt procedure had two arguments where expmod had three so I figured part of the computation was being moved around. I even realized that Alyssa's way went ahead and computed the base to the exponent and then tested the remainder against it once. That just seemed like it should've been better to me. I didn't have the sense to just add runtime in as an argument and see how much time they were taking. At any rate, the original expmod does lots of little remainder tests but because of Bignum arithmetic that ends up being faster than a single test on a huge number.


1.26:

(expmod base (/ exp 2) m) has to be evaluated an extra time each time the (even? exp) condition evaluates to true. This moves the algorithm from log n to n because, as I somewhat foolishly missed, it shifts the recursion from a linear recursion to a tree recursion. See the SICP Wiki's solution for more detail, it seems to be the best resource for rigorous complexity analysis.


1.27:



(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m)) m))
(else
(remainder (* base (expmod base (- exp 1) m)) m))))
;Value: expmod

(define (carmichael-test n)
(define (try-it a)
(= (expmod a n n) a))
(define (carmichael-iter times)
(cond ((= times 0) true)
((try-it times) (carmichael-iter (- times 1)))
(else false)))
(carmichael-iter (- n 1)))
;Value: carmichael-test

1.28:



(define (expmod base exp m)
(define (miller-rabin x)
(and (not (= x 1)) (not (= x m)) (= (square x) (modulo 1 m))))
(cond ((= exp 0) 1)
((even? exp)
(if (miller-rabin (square (expmod base (/ exp 2) m)))
0
(remainder (square (expmod base (/ exp 2) m))
m)))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
;Value: expmod

(define (miller-rabin-search n)
(define (try-it a)
(= (expmod a (- n 1) n) 1))
(try-it (+ 1 (random (- n 1)))))
;Value: miller-rabin-search

(define (miller-rabin-test n)
(define (mr-iter count)
(cond ((= count 1) #t)
((miller-rabin-search n) (mr-iter (- count 1)))
(else #f)))
(mr-iter (floor (/ n 2))))
;Value: miller-rabin-test

;;I got everything written right on this one but I had to check Ken's page again to notice that my try-it definition was
;;testing the expmod result against a, not 1. Once I fixed that I was right as rain.

As a final note, I should point out that my solution here differs a bit from the norm. One, I'm pretty serious about not using primitives that haven't been introduced yet. Even Ken Dyck's solution uses let (though the SICP wiki avoids it). After all, this is my first serious work in programming ever. The closest thing besides this was my read through the first chapter of K&R in summer of 2006. Anyway, just keep in mind I'm taking this as my formal education.

Living with Ben
posted on 2008-02-29 00:24:09
Living with Ben was pretty bad ass. We stayed up late arguing about stuff that only one of us really knew anything about (computers or philosophy), made crazy playlists, played smash bros, and generally had lots of fun. Dan was awesome too but he just hid in his room a lot and then popped out and surprised everybody with amazingness. You wouldn't know it from looking at the guy but he was totally the comic relief.

I mention this though because Ben and I might end up living together again sometime after May. I'm for it. And just so you all know, I'm really hoping to live within around Peachtree Industrial, near Oglethorpe. So, if you know good apartment complexes, guest houses, etc, Holla.

Anyway, we worked on this one playlist for like...two weeks or something? I don't know. We came up with a first version which was pretty bad ass by itself but it diverted from the direction I had in mind originally (it started off as my baby) after the Broken Social Scene track...or maybe the Ambulance LTD track. Long story short, I spent another few days to come up with this Version 2 which pretty much sticks to my original vision. Here it is for your thoughts and enjoyment:


1. The Faces - Ooh-ooh-la
2. Blind Melon - No Rain
3. Fastball - Out Of My Mind
4. The Five Stairsteps - O-o-h Child
5. Marvin Gaye - Where Are We Going
6. The Beatles - Come Together
7. Ambulance LTD - Young Urban
8. Broken Social Scene - Looks Just Like The Sun
9. Psapp - Tricycle
10. Massive Attack - Teardrop
11. Corinne Bailey Rae - Trouble Sleeping
12. Regina Spektor - On The Radio
13. Gnarls Barkley - St.Elsewhere
14. Jamie Lidell - What's The Use
15. Elliot Smith - Son of Sam
16. Ambulance LTD. - Arbuckles Swan Song
17. Cat Power - Willie
Quote Post
posted on 2008-02-28 18:08:57
This is probably the most succinct way to put what I'm, in part, getting at. Make no mistake, I will flesh out that essay...it just might take a while. For now, I'm back to programming. More soon though guys.

"Civilization advances by extending the number of important operations which we
can perform without thinking about them."
–Alfred North Whitehead

This quote sourced from one of Richard Gabriel's essays, Objects Have Failed. It also appears in The Road Less Taken.
Secondhand Standards
posted on 2008-02-27 05:27:22

Every now and then I see, hear, or read something that sets my brain on fire. I find some connection that I didn't notice before and go off exploring. It happened a week or two ago over lunch at work. Occasionally there are lunch meetings around work-related activities that you can voluntarily attend. This particular lunch had us watching Paul Hawken's speech at Greenbuild 2007. It set the old wheels turning and the dominos toppling over. This is what spilled out...


For me, I think this all started formally with Thoreau. He was the first person who promoted an idealogy that I both a) actually heard and b) identified with. This would've been in the 11th grade. Prior to this I was more or less an anarchist and held no ethos as my own. Long story short, I've moved on but the transcendentalists sort of hold a special place in my heart. And the thing is, while I've hung onto Walden like a treasure I haven't read it in too long. So when Paul Hawken started mentioning transcendentalists in his speech it was a moment of revelation for me as I came full circle.


There's a crystallization of my beliefs here that has taken years and is an ongoing journey so bear with me. The older I've grown the more interest I've taken in the notion of Historical Progress, or at the very least, of charting where the universe has been and where it's going. Particularly in the last two years or so, thinking about forms of social organization and things like Robert Wright's Nonzero and Ray Kurzweil's The Singularity is Near have been interesting brain food. Of course, I've also been following Open Source, flirting with the environmentalists, and trying to figure out the lispers. And I think I see what I identify with and agree with in it all.


You see, I have this 90% theory. The theory states that at least 90% of human labor is expended to maintain the status quo and that only a fraction of our energy can go to what we care about or to new and creative things. This has come about because of increasingly complex social strata emerging as political and economic forms cave under the growth of civilization. Not western civilization but all civilization. It's a growing interdependency as Robert Wright describes.


He's more or less nailed it. And this interdependency has occurred through large centralized institutions (particularly corporations and governments) that have driven forward economic progress at the price of independence. It's much harder in the 21st century to figure out how to completely sustain yourself in your basic survival needs without withdrawing from society altogether. The sort of experimentalism that was possible by providing for oneself outside of the traditional means is no longer a realistic goal. We have boxed ourselves in.


This seems to me an ethical issue. It is not an ethical issue because consumerism or capitalism is wrong but because one of the lauded premises (whether actual or not) of our nation was some increased degree of influence over one's destiny. In the present day, this influence is lacking if one wants to live in a social setting but with strong self-provision of needs. This frontier opportunity has gone missing on both the frontier of new societal forms and the independent pursuit of sustenance through life, liberty, and happiness.


This is not, it is important to note, the fault of capitalism or democracy. Rather, these are the limits of these systemic forms under burdens of complexity they are not equipped to handle. They have become our Golden Hammers. (A recent e-mail from a dear friend and former teacher of mine eloquently expresses distress over this fact.) In short, the promised revolutionary nature of America has been lost. The Internet is another thing that has been lauded as inherently free. And like the FSF and Open Source this meant free in the context of freedom, libre, not free as in beer.


Lawrence Lessig was the first to note to us that the internet is not inherently free. That being a man-made thing, like a government, the internet was subject to our control and thus could have its freedom removed. Whether or not that is occurring right underneath us remains a subject of debate. I contend, however, that is has already occurred with regards to our nation and, thanks to globalization, much of the "westernized" world. We are buried under the mountains of our own bureaucracy; democracy and capitalism have become organizational forms which limit our innovation and our efficiency. Most importantly, this has impeded our capacity to do what we love.


And I feel like that is what the transcendentalists realized so long ago. They saw it coming and just maybe saw some of the things we stood to lose. Paul Hawken says Emerson realized that "It's all connected". That's why Thoreau reasoned his way into jail, because if he paid taxes while Texas Rangers raped Mexican women he figured it made him a rapist. That's why my friend Alexa saw people in South America who lived in poverty and slept on the job and instead of asking why they weren't like us, asked why we weren't like them. And that's why Richard Stallman found ethics in software (namely a printer driver). It's why a British journalist decries college and lispers wage a near religious war on tedium and repitition.


These all seem like strange places to find ethics. And maybe they are. But this seems to be the strand that ties together article after article I read about why college is unnecessary or high school is drudgery or work is slavery. And I think if I had to give it a name, I could only call it Efficiency. Because we're just not as efficient as we'd like to be. We've finally lost the right to enough of our time that we're jealous about it. There's a recognition that there should be a way to keep society going without all of us dedicating all our time to make sure that it's still there tomorrow. And in come the environmentalists, shouting about the world we leave our children, talking about building to last.


And if there is one question I'm interested in answering it's this: Surely, there is a way for us to restructure society so that only 70% of human labor or 50% or less has to go to maintaining the status quo. Right? Then the rest could go to creativity or innovation or progress or us. I think there is and I'm not opposed to spending my life trying to answer the question. There do thankfully seem to be a number of revolutionary trends coming about, some of which are already well in swing. But it's late, I have work tomorrow, and much as I'd love to I have to call this a wrap for one night.

Tutorials I’ve been meaning to do…
posted on 2008-02-26 21:50:16
as part of a getting things done streak. You know? Like, learn x y per z. Anyway, aside from reading SICP and writing code, getting it posted on here, and getting this essay up these are the other thing I've been lagging on:
An Emacs Tutorial
Git Tutorial Part 1
Git Tutorial Part 2
A Much more focused collection of *nix & associated utilities sheets
A Massive Index of Cheat Sheets

Also, I'm not sure I buy it but there was some pretty optimistic news about Concentrated Solar Power today. I'd love to see more detailed plans and a price/time-to-completion estimate.

Finally, if anyone has any insights about why I'm getting a bad EIP value and a kernel panic whenever I try to transfer large files (or dozens of songs) with my server, feel free to let me know. I will buy you a (coffee/beer/etc). It seems related to this issue from an openSuse user. It could also be related to me using the 8139cp module instead of 8139too for my ethernet card. Whatever, I doubt i'll get anywhere but I'll be looking into it.

Now to grab dinner and finish that essay...
2 Years later…
posted on 2008-02-26 17:42:19
and the NSA/Telcos lawsuits are still going. The Bush Administration is still saying it was necessary to wiretap the phones of hundreds of millions of Americans without warrants. The Government is still pushing to grant retroactive immunity. And it's generally a whole big mess. Doesn't anyone (in our Government) care about privacy or the violation of the Constitution?

Sorry I haven't posted in so long (11 days). I guess I've been distracted. An essay I've working on should be up soon, as should a code/sicp update.

Here are some things to chew on and yell at your local politicans about:
Myth/Facts about Retroactive Immunity
Republicans block FISA talks
Telecom Immunity Passes in the Senate
Domestic Call Database started before 9/11

Seriously, just click yell at your local politicians if you want to help.
One More Reason
posted on 2008-02-15 18:44:31
I knew this day would come sooner or later. I finally ran up against a task that was perfect to use Unix Pipes for. I needed to rename 2335 MP3s and I did it in 1 minute and 40.686 seconds.

Here's the backstory:
I recently got a new MP3 player because my old one died. When I got my last MP3 player I had selected the 2000 songs I actually liked and regularly listened to out of my 17000 or 18000 and copied them to the MP3 player and my PS3. Those songs were sort of a pain to get off my PS3 onto the new player so I figured I might as well keep a separate copy of them somewhere on my desktop. Eventually I'm planning on moving them to my server as well at which point Redline Radio will get up and running again!

Anyway, I copied all the files off of my new MP3 player to my desktop to create said separate copy and found that the filename on each song had been changed to SONG_NAME.b-mtp-XXXX where the X's were the song numbers up to 2335. I'll be damned if I was going to rename all those by hand. So, I thought I'd use Unix Pipes which allow you to take the output from one command and feed it into another command. And just for fun, I timed it.

To time a command you just put the word time in front of it. So to time the change directory command you'd type, "time cd DIRECTORY". To rename all those files I would use the rename command, but it would only rename one file at a time or at best one directory. I had a few hundred directories. So, I needed a command that would find each file by searching through the directories and find is the perfect command for the job. I can call find and tell it to search for files with that weird extension and then each time it does, run rename on the file with a regular expression to change that extension to mp3. And here's how that looks:

time find ./ -type f -exec rename 's/b-mtp-[0123456789]*/mp3/' {} ;

That's it. It says time the find command searching from this directory down for files (ignoring directories, etc) and when you find one rename it based on this regular expression. Done. 2000 files renamed in 2 minutes. And people wonder why I use Linux. Yes, Apple Automator does do this. But do you know why the robot icon for Automator is holding a pipe? That's right. It's an homage to Unix Pipes. You could of course do this in Apple's Terminal. That would be pretty cool. You hear me Dobbs?

Anyway, I've been thinking a bit about Alan Perlis' Programming Epigram: "A language that doesn't affect the way you think about programming, is not worth knowing." And I think there's an analogue for Operating Systems as well in all likelihood. Text editors, too (here comes the Vi vs. Emacs crowd). So, I may be using a blub operating system but I haven't soaked up all I can learn from it yet. I just need to remember to try other things too.

Just for fun, here's one more. This one outputs the 50 largest directories on my hard drive and their sizes to a text file on my desktop. du is Disk Usage, the -S option tells it to not to include subdirectories (so I only get leaves and not branches of the filesystem tree in my results). | passes output from one command as input to the next so | sort -nr passes the list of the directories and their sizes to sort which thanks to the nr switch sorts them in Reverse Numerical order. Greatest first, right? Then | head -n50 takes that output and cuts off everything after the first 50 lines. Finally, > dumps the final output into a text file at the location given. Ta da.

du -S / | sort -nr | head -n50 > /home/redline/Desktop/50large.txt
For Don and Lex
posted on 2008-02-14 04:18:01
Eduardo Galeano, Voices of Time, Soul in Plain Sight, pg.98:

"According to an ancient belief, the tree of life grows upside down. Its leaves burrow into the earth, its roots gaze at the sky. It offers not its fruits but its origins. Rather than hiding underground what is most intimate, most vulnerable, it bares its roots, exposing them to the winds of the world.
"That's life," says the tree of life."

I haven't fallen off the face of the earth just yet. More soon guys. I'm hoping to get a SICP progress update posted this weekend as well as (maybe) a REAL ESSAY on REAL THINGS!

Expect me to tie together transcendentalists, the green and possibly civil rights movements, and lisp. Yeah, who knows.
Pascal’s Triangle
posted on 2008-02-07 03:25:28

A little over two weeks ago I came up against Exercise 1.12 in the venerable Structure and Interpretation of Computer Programs.


The exercise wants you to write a recursive program to compute elements of Pascal's Triangle.


This exercise has pretty much infuriated me and it's all my own fault. Upon first hearing the problem statement I got it in my head that the function should look something like "(define (pas n)...)". I always think of number series being described in terms of a single argument (i.e. the 12th element) so it seemed natural to me that the pascal's triangle function should be computed in this way even though it is not, in some sense, a traditional series.


After a while, I cracked and read the precursor text (but not the code) to Eli Bendersky's solution and noticing that he defined the function with two arguments (for columns and rows) arrived fairly quickly with that insight at what seems to be the more or less standard solution. I have had this much completed for a week but gotten stalled trying to figure out the problem of a pascal function that takes one argument.


As of today I've solved the problem though and hoped to share my results here. First, the throwaway code that ended up being good for nothing!



(define (is-one? element)
(define (is-one-iter ones count flag)
(cond ((< element 5) #t)
((= ones element) #t)
((> ones element) #f)
((= flag 1) (is-one-iter (+ ones 1) count (- flag 1)))
(else (is-one-iter (+ ones count) (+ count 1) (+ flag 1)))))
(is-one-iter 4 2 0))
;Value: is-one?

That code tests to see whether a given element equals one and it does take a single argument which is nice. I couldn't figure out a way to use it to compute the actual elements though.


After a little bit of experimenting I stumbled on this number sequence (OEIS #A080956) which when put in the following procedure would allow me to compute n from a given column and row.


EDIT: Corrected dyslexic mistake in my code (I'd replaced all instances of col with row and vice versa). See comments.



(define (n-from-rowcol row col)
(define (f x)
(- (/ (* (+ x 1) (- 2 x)) 2)))
(+ row col (f (- row 1))))
;Value: n-from-rowcol

Now all I had to do was find a way to reverse the function to give me the inputs if I gave it the output. I actually stumbled upon another number sequence (OEIS #A000124, also known as the Lazy Caterer's Sequence) which when put into the following procedure returns the correct column and row for a given element. At last, working code:



(define (pascal n)
(define (pas col row)
(cond ((= col 1) 1)
((= row 1) 1)
((= col row) 1)
(else (+ (pas (- col 1) row)
(pas (- col 1) (- row 1))))))
(define (colrow-from-n)
(define (col-iter count)
(define (f x)
(- (/ (+ (square x) x 2) 2) x))
(cond ((> (f count) n) (pas (- count 1) (- n (- (f (- count 1)) 1))))
((= (f count) n) (pas (f count) 1))
(else (col-iter (+ count 1)))))
(col-iter 1))
(colrow-from-n))
;Value: pascal

Any insights into cleaner code, better algorithms, or comparisons between the two number series are welcomed.

This blog covers 2015, Books, Butler, C, Dad, Discrete Math, Displays, Education, Erlang, Essay, Gaming, Gapingvoid, HTDP, Hardware, IP Law, LISP, Lecture, Lessig, Linkpost, Linux, Lists, MPAA, Milosz, Music, Neruda, Open Source, Operating Systems, Personal, Pics, Poetry, Programming, Programming Languages, Project Euler, Quotes, Reddit, SICP, Self-Learning, Uncategorized, Webcomic, XKCD, Xmas, \"Real World\", adulthood, apple, careers, coleslaw, consumption, creation, fqa, games, goals, heroes, injustice, linux, lisp, math, melee, metapost, milosz, personal, poetry, programming, ragequit, recreation, rip, strangeloop, work

View content from 2015-05, 2015-03, 2015-02, 2015-01, 2014-11, 2014-09, 2014-07, 2014-05, 2014-01, 2013-10, 2013-09, 2013-07, 2013-06, 2013-05, 2013-04, 2013-03, 2013-01, 2012-12, 2012-10, 2012-09, 2012-08, 2012-06, 2012-05, 2012-04, 2012-03, 2012-01, 2011-10, 2011-09, 2011-08, 2011-07, 2011-06, 2011-05, 2011-04, 2011-02, 2011-01, 2010-11, 2010-10, 2010-09, 2010-08, 2010-07, 2010-05, 2010-04, 2010-03, 2010-02, 2010-01, 2009-12, 2009-11, 2009-10, 2009-09, 2009-08, 2009-07, 2009-06, 2009-05, 2009-04, 2009-03, 2009-02, 2009-01, 2008-12, 2008-11, 2008-10, 2008-09, 2008-08, 2008-07, 2008-06, 2008-05, 2008-04, 2008-03, 2008-02, 2008-01, 2007-12, 2007-11, 2007-10, 2007-09, 2007-08, 2007-07, 2007-06, 2007-05


Unless otherwise credited all material Creative Commons License by Brit Butler