;;;; In a computer science course at Catonsville Community College, I had to
;;;; write functions to add, subtract, multiply, divide, modulo, exponentiate,
;;;; get the greatest common denominator, and get the least common multiple,
;;;; with the catch that I could only use the built in addition and subtraction
;;;; operators once each, to add (or subtract) exactly one, and I couldn't use
;;;; any of the other builtin operators for the functions I was writing.  All
;;;; operations would be on positive integers and would return integers.
;;;; I set myself two additional tasks: I would deal with all integers, both
;;;; positive and negative, and I would match the interfaces of the equivalent
;;;; functions in Common Lisp.
;;;;
;;;; This is the code I wrote for the course.

(defun add-one (n)
  (1+ n))

(defun sub-one (n)
  (1- n))

(defun add (&rest ns)
  (if (null ns)
      0
      (add-pair (car ns) (apply #'add (cdr ns)))))

(defun add-pair (n1 n2)
  (if (zerop n2)
      n1
      (if (minusp n2)
	  (add-pair (sub-one n1) (add-one n2))
	  (add-pair (add-one n1) (sub-one n2)))))

(defun sub (n1 &rest ns)
  (if (null ns)
      (make-neg n1)
      (add n1 (sub (apply #'add ns)))))

(defun make-neg (n1)
  (if (zerop n1)
      0
      (if (minusp n1)
	  (add-one (make-neg (add-one n1)))
	  (sub-one (make-neg (sub-one n1))))))

(defun mult (&rest ns)
  (if (null ns)
      1
      (mult-pair (car ns) (apply #'mult (cdr ns)))))

(defun mult-pair (n1 n2)
  (apply #'add (list-nums n1 n2)))

(defun list-nums (n1 n2)
  (if (minusp n2)
      (list-nums (sub n1) (sub n2))
      (if (zerop n2)
	  nil
	  (cons n1 (list-nums n1 (sub-one n2))))))

(defun div (n1 &rest ns)
  (if (null ns)
      (if (minusp n1)
	  -1
	  0)
      (div-pair n1 (apply #'mult ns) 0 0)))

;; This really behaves like the floor function.
;; Well, it ought to, at least.

;; n1 is to be divided by n2.  ans is the current guess at an answer.
;; rel indicates the relation of the last calculated value to the real one.
;;  -1 if the guess was low, 1 if the guess was high, and 0 if unknown.

(defun div-pair (n1 n2 ans rel)
  (cond
    ((zerop n2)
     nil)
    ((minusp n2)
     (div-pair (sub n1) (sub n2) ans rel))
    ((zerop rel)
     (if (< (mult n2 ans) n1)
	 (div-pair n1 n2 ans -1)
	 (if (> (mult n2 ans) n1)
	     (div-pair n1 n2 ans 1)
	     ans)))
    ((minusp rel)
     (if (> (mult n2 (add-one ans)) n1)
	 ans
	 (div-pair n1 n2 (add-one ans) rel)))
    ((plusp rel)
     (if (< (mult n2 (sub-one ans)) n1)
	 (sub-one ans)
	 (div-pair n1 n2 (sub-one ans) rel)))))

(defun my-mod (n1 n2)
  (sub n1 (mult (div n1 n2) n2)))

(defun my-pow (n1 n2)
  (if (minusp n2)
      (div (my-pow n1 (sub n2)))
      (apply #'mult (list-nums n1 n2))))

(defun my-gcd (&rest is)
  (case (length is)
  (0 0)
  (1 (car is))
  (2 (gcd-pair (car is) (cadr is)))
  (otherwise (my-gcd (car is) (apply #'my-gcd (cdr is))))))

(defun gcd-pair (i1 i2)
  (cond
    ((minusp i1)
     (gcd-pair (sub i1) i2))
    ((minusp i2)
     (gcd-pair i1 (sub i2)))
    (t
     (if (< i1 i2)
	 (gcd-pair i2 i1)
	 (if (zerop (my-mod i1 i2))
	     i2
	     (gcd-pair i2 (my-mod i1 i2)))))))


(defun my-lcm (&rest is)
  (if (null is)
      1
      (div (apply #'mult is) (apply #'my-gcd is))))