?

Log in

No account? Create an account
Soft clay - Lindsey Kuper [entries|archive|friends|userinfo]
Lindsey Kuper

[ website | composition.al ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Soft clay [Jul. 2nd, 2008|03:13 pm]
Lindsey Kuper
[Tags|]

I got three more SICP problems done on the plane on the way to Atlanta. That's 28 done, 19 to go in chapter 1!

When I first started doing this, it all seemed pretty much equally hard, but now I'm starting to get a better feel for what my strengths and weaknesses are. Sneaky optimizations and tricky too-clever-by-half algorithms don't come naturally to me; problems like this one take days and make me tear my hair out. I can't wait to be done with the accursed "Testing for Primality" section, which keeps being all, "Faster. Did you make it faster? Okay, why is it faster? Prove it. Now make it even faster. Now do it probabilistically. Now do it probabilistically a different way (and faster). What's the running time? Do your data bear this out?" I'm learning a lot, I suppose, but...I'm pretty sure the world already knew that 1,000,037 was a prime number, you know? At least I can say that I've joined one of the most hallowed traditions of scientific research, in that "Do your data bear this out?" has become my new least favorite question.

So it was a breath of fresh air to finally work on a problem like this:

(define simpsons-rule
  (lambda (f a b n)
    (letrec ((h (/ (- b a) n))
             (y (lambda (k)
                  (f (+ a (* k h)))))
             (next-coefficient (lambda (k)
                                 (if (even? k) 
                                     2
                                     4)))
             (finalize (lambda (f a n summation)
                         (* (/ h 3) 
                            (+ summation
                               (f a)                 ; y_0
                               (f (+ a (* n h))))))) ; y_n
             
             (kernel (lambda (f a b n k accumulator)
                       (if (= k n)
                           (finalize f a n accumulator)
                           (kernel f a b n (+ k 1) 
                                      (+ accumulator 
                                         (* (next-coefficient k) 
                                            (y k))))))))
      (kernel f a b n 0 0))))

(define (cube x) (* x x x))

(simpsons-rule cube 0 1 100) and (simpsons-rule cube 0 1 1000) both return 1/4, which is the exact value of the integral. (In fact, an n as low as 6 seems to work.) This code basically wrote itself -- as fast as I could think it1 -- ten minutes -- amazing -- effortless -- like soft clay in my hands. Look, you guys, I barely even understand what an integral is, okay? But that's the point: it doesn't matter! This is why higher-order programming is so cool!


  1. Lindsey: "Most of the time, I can't code as fast as I can think, but I get the sense that you can."
    Alex: "Oh, I can code much faster than I can think! That's the problem!"
LinkReply