I've found a really strange situation with the program below. It's
running on a Sun Sparcstation with Sun Common Lisp 4.0.
For seemingly arbitrarily large numbers, it appears to return the proper
values---e.g. (diagonal 17) => 1/5 , (diagonal 1000) => 35/10 , etc.
But when I try something absurdly large, say
(diagonal 10000000000000000000000000)
after some considerable crunching it kicks out with:
>>Error: #<Unknown-Object 13380F6> should be a LIST
+:
Rest arg 0 (RESTARG): (116036045028828 . #<Unknown-Object 13380F6>)
:C 0: Use a new value
:A 1: Abort to Lisp Top Level
which has me *completely* baffled. Any ideas? Is there an error in
the program? (I'm sure it can be more efficiently or properly written
stylistically.)
Thanks for any clues!
Brendan
-- cut --
;;;
;;; DIAGONAL --- find the nth entry in a diagonally-listed matrix of
;;; rational numbers, of the form:
;;; 0/1 0/2 0/3 0/4 ... => 0/1 0/2 1/1 2/1 1/2 0/3 etc
;;; 1/1 1/2 1/3 1/4 ... Looping up & around like:
;;; 2/1 2/2 2/3 2/4 ... start 1 2 6 7
;;; 3/1 3/2 3/3 3/4 ... 3 5 8
;;; ... ... ... ... 4 9
;;; etc
;;;
;;; We rely upon the fact that the nth entry lies on the row that corresponds
;;; to the nearest (but not greater) Fibonacci number. Then from there it's
;;; easy to figure out the numerator and denominator from the row we're on
;;; and what fibonacci it corresponds to. (A catch, though, comes when going
;;; from the left to the right---see below.)
;;;
;; A normal fraction in the table looks like:
;;
;; proper_fibonacci - n_desired
;; --------------------------------------
;; row - proper_fibonacci - n_desired
;;
;; If we're on an even row, that means we're looping down->up, so the
;; numbers are no longer of the form above; instead, they now look like:
;;
;; n_desired - (up_one_fibonacci - row_currently_on) - 1
;; ---------------------------------------------------------
;; row - proper_fibonacci - 1
(defun diagonal (n)
;; climb up until we hit the Fibonacci closest to n
(let ((v 0) (c 0))
(loop while (> n v) do
(progn (setf v (+ v c)
c (1+ c))))
;; the loop kicks out at one past the fibo we want
(setq row (1- c))
;; if it's an even row, use the funky method; the hack of (- n (- v row) 1)
;; will get us the fibonacci that's the closest to n (e.g. if we do 17,
;; that will give us 15)
(if (= (mod row 2) 0) (setq diff (- n (- v row) 1))
(setq diff (- v n))))
;; smile at the nice user
(format t "Fraction ~D is ~D/~D~%" n diff (- row diff)))
-- cut --
--
Brendan Kehoe - Widener Sun Network Manager - ·······@cs.widener.edu
Widener University in Chester, PA A Bloody Sun-Dec War Zone
". . . if you were a gas, you would be inert." -- Dieter