;;;; 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))))