Crouching Euler, Hidden Closure

The Hacking Hat has been delving into Project Euler and I had to see what I could do with it– just to gauge whether or not SICP and Dominus are doing me any good.

My first attempt, I just read the problem and tried not to look at where the Hat was going with it:

(defun square (n) 
  (* n n))       

(defun sum-first-n-squares (n) 
  (cond ((< n 1) 0) 
        (t (+ (square n) 
              (sum-first-n-squares (1- n))))))       

(defun problem-6a () 
  (let ((x (sum-first-n-squares 100))) 
    (- (square x) x)))

I used a simple recursive function to do the job… but because I was just doing one quick problem, I didn’t even think of applying any functional techniques.

I love lists, though. They are just so handy and easy to deal with. They also force the computer to “show its work” at each step of the process. Besides, we might want to make a list of the first n cubes or something and then do several things with it.

(defun first-n-fns (n fn) 
  (cond ((< n 1) '()) 
        (t (cons (funcall fn n) 
              (first-n-fns (1- n) fn)))))       

(defun problem-6b () 
  (let ((x (apply #'+ (first-n-fns 100 #'square)))) 
    (- (square x) x)))

The problem with this approach is that there’s a limit to how many arguments the plus function can stand. I couldn’t get mine to take too much more than a couple of thousand. For the next attempt, I tried making an iterative function that took two functions for arguments– the transformation function to be applied to each number in the series and the operation to be applied to the entire list:

(defun operate-on-series (operation from to transformation initial-value) 
  (if (> from to) 
      initial-value 
      (operate-on-series operation 
                         (1+ from) 
                         to 
                         transformation 
                         (funcall operation 
                                  initial-value 
                                  (funcall transformation 
                                           from)))))       

(defun problem-6c () 
  (let ((x (operate-on-series #'+ 1 100 #'square 0))) 
    (- (square x) x)))

Just for grins, I decided to implement the exact same thing, but using a closure this time to make an iterator:

(defun make-iterator (from to transformation) 
  (let ((n (1- from))) 
    (lambda () (if (>= n to) 
                    '() 
                    (progn (setf n (1+ n)) 
                           (funcall transformation 
                                    n))))))       

(defun operate-on-iterator (op iterator &optional (initial 0)) 
  (let ((x (funcall iterator))) 
    (if (null x) 
        initial 
        (operate-on-iterator op 
                             iterator 
                             (funcall op initial x)))))       

(defun problem-6d () 
  (let ((x (operate-on-iterator #'+ (make-iterator 1 100 #'square)))) 
    (- (square x) x)))

Surprisingly, the final version using the closure seemed to be the most powerful. I couldn’t get any of the other versions to take near as large numbers. Then I realized that this was because the closure was a compiled function and the rest weren’t, so I used the compile-file function to make a .fas file. I loaded that one up and found that the straight iterative solution was actually superior to the closure/iterator version:

CL-USER> (time (operate-on-series #’+ 1 10000000 #’square 0))
Real time: 8.063119 sec.
Run time: 7.8125 sec.
Space: 347655180 Bytes
GC: 663, GC time: 2.796875 sec.

333333383333335000000

CL-USER> (time (operate-on-iterator #’+ (make-iterator 1 10000000 #’square)))
Real time: 10.516433 sec.
Run time: 9.78125 sec.
Space: 347655236 Bytes
GC: 663, GC time: 2.75 sec.

333333383333335000000

Interesting results… but I’m sure that denizens of the world-wide SICP study network could offer up ideas for further improvements….

UPDATE: I of course made an incorrect assumption in reading the problem. After seeing the example on the Euler site, I understand what they were really looking for. Of course… it’s easy to modify my code to give the correct answer in the functional designs:

(defun problem-6b () 
  (- (square (apply #'+ (first-n-fns 100 #'identity))) 
     (apply #'+ (first-n-fns 100 #'square)))) 

(defun problem-6c () 
  (- (square (operate-on-series #'+ 1 100 #'identity 0)) 
     (operate-on-series #'+ 1 100 #'square 0))) 

(defun problem-6d () 
  (- (square (operate-on-iterator #'+ (make-iterator 1 100 #'identity))) 
     (operate-on-iterator #'+ (make-iterator 1 100 #'square))))
Advertisements

One Response to “Crouching Euler, Hidden Closure”

  1. FOO Says:

    Use REDUCE instead of APPLY.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: