Yesterday I wrote about the Trabb Pardo Knuth algorithm and gave an implementation in Emacs Lisp. Elisp allows an nice implementation but was a bit frustrating because the Elisp interpreter handles overflows internally and never signals an
overflow condition. Therefore, I decided to try it in Common Lisp to see how they differ and also to force an overflow.
You can’t get an integer overflow in Common Lisp because of the bignum support but you can with floating point calculations. Here’s my CL implementation of the TPK algorithm. I tried to make it as much like the Elisp version as possible.
(defun tpk () (let ((s (make-array 11))) (dotimes (i 11) (princ "Enter number: " *query-io*) (setf (svref s i) (read *query-io*))) (map nil (lambda (n) (print (handler-case (expt 2.0 n) (floating-point-overflow () "OVERFLOW")))) (reverse s))))
One nice thing about CL is that
reverse works on any simple sequence and thus works on vectors. On the other hand, there isn’t a
read-number function so I had to use
parse-integer instead. Also, the CL
mapc requires lists so I used
map, which accepts vectors, instead.
When I ran
tpk, I got gratifying results.
CL-USER> (tpk) Enter number: 1 Enter number: 10 Enter number: 100 Enter number: 200 Enter number: 300 Enter number: 400 Enter number: 500 Enter number: 600 Enter number: 700 Enter number: 800 Enter number: 900 "OVERFLOW" "OVERFLOW" "OVERFLOW" "OVERFLOW" "OVERFLOW" "OVERFLOW" "OVERFLOW" "OVERFLOW" 1.2676506e30 1024.0 2.0 NIL
Update: Pascal Bourguignon pointed out that the specification said to read in numbers not integers so I’ve fixed the code above to use
read rather than
(parse-integer (read-line *query-io*)).