How do I convert a decimal number to a list of octal digits in Common Lisp?

Question

I need to have the result in correct order. It works for numbers less than 100 only.

(base8 8) gives (1 0),

(base8 20) gives (2 4),

but (base8 100) gives (414) instead of (144).

I tried for 2 days and can not find the problem. Please help me.

(defun base8(n) 
  (cond
    ((zerop (truncate n 8)) (cons n nil))  
    (t (reverse (cons (mod n 8)
                      (base8 (truncate n 8)))))))

Answer 1

The problem is that you are reversing the string a few times. The following will do:

(defun base8 (n)
  (let ((t8 (truncate n 8)) (m8 (mod n 8)))
    (if (= t8 0) 
      (list m8)
      (append (base8 t8) (list m8)))))

EDIT

Here's a solution without append, using a helper function. You'll see clearly that one reverse is enough:

(defun base8-helper (n)
  (let ((t8 (truncate n 8)) (m8 (mod n 8)))
    (cons m8 (if (= t8 0)
               nil
               (base8-helper t8)))))

(defun base8 (n)
  (reverse (base8-helper n)))

or, with an accumulator (tail-recursive)

(defun base8 (n &optional (acc '()))
  (let ((t8 (truncate n 8)) (m8 (mod n 8)))
    (if (= t8 0)
      (cons m8 acc)
      (base8 t8 (cons m8 acc)))))