SICP Section 1.2

Tagged as LISP, Self-Learning, SICP

Written 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.

comments powered by Disqus

Unless otherwise credited all material Creative Commons License by Brit Butler