A Couple of Fun Programs

[Dick Gabriel <RPG@SAIL.STANFORD.EDU>]

Jonathan sent out an interesting program the other day, and I was prompted
to send two more. These are (ugh, bletch) Common Lisp programs, but I
think it's instructive to see that CL programs don't have to look
completely silly (not using DO loops, &-constructs, &tc).  It's your job
to figure them out without running them. LABELS is like LETREC, TRUNCATE
rounds towards 0, (VALUES x y z) returns three values, and
(MULTIPLE-VALUE-BIND (X Y Z) (RETURN-THREE-VALUES) . <forms>) binds the
three variables X, Y, and Z appropriately and executes <forms>.

(defun f (n)
 (labels ((f (n m)
           (if (= n m)
	       n
	       (let ((h (truncate (+ m n) 2)))
		 (* (f n h) (f (+ h 1) m))))))
   (f 1 n)))

(defun f (i)
 (labels ((g (n n-1 n-2 m m-1 m-2)
           (let ((k (* n-1 m-1)))
	    (values (+ (* n m) k)
		    (+ (* n m-1) (* n-1 m-2))
		    (+ k (* n-2 m-2)))))
	  (h (i)
           (cond ((zerop i) (values 1 0 0))
		 ((= i 1) (values 1 1 0))
		 ((evenp i)
		  (multiple-value-bind (n n-1 n-2)
	           (h (truncate i 2))
	           (g n n-1 n-2 n n-1 n-2)))
		 (t
		  (multiple-value-bind (n n-1 n-2)
	           (h (1- i))
	           (g 1 1 0 n n-1 n-2))))))
  (prog1 (h i))))

They are written using non-instructive variable names. 

				-rpg-