Lindsey Kuper (lindseykuper) wrote,
Lindsey Kuper

Soft clay

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) 
             (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!"
Tags: programming

  • Some victories

    In the last two days: I sent a draft of my dissertation to my committee! There are some parts that aren't quite finished; it's a…

  • My dissertation abstract

    So I need to write an abstract for my dissertation. Anyone wanna glance over this and tell me what you think? If you suggest any edits, keep in…

  • What December's been like so far

    Alex oniugnip has already written about what December has been like for us so far. Here's the story from my perspective. At the…

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded