;;;; -- Division ------------------------------------------------------------------------------

;; Since the most negative word cannot be negated our algorithm is
;; formulated for negative numbers. And as every positive number could
;; be negated, division of positive numbers is done by just negating
;; them. Mixed sign division follows.

(defun / (a b)
  ;; This does what FLOOR does.
  (if (< a 0)
      (if (< b 0)
          (ndivmod a b 0)
          (- -1 (ndivmod a (- b) 0)))          ;mixed signs
      (if (< b 0)
          (- -1 (ndivmod (- a) b 0))           ;mixed signs
          (ndivmod (- a) (- b) 0))))

(defun mod (a b)
  (let (r)
    (if (< a 0)
        (if (< b 0)
            (progn (ndivmod a b (& r)) r)
            (progn (ndivmod a (- b) (& r)) (+ b r)))
        (if (< b 0)
            (progn (ndivmod (- a) b (& r)) (- b r))
            (progn (ndivmod (- a) (- b) (& r)) (- r))))))

(defun rem (a b)
  (let (r)
    (if (< a 0)
        (if (< b 0)
            (progn (ndivmod a b (& r)) r)
            (progn (ndivmod a (- b) (& r)) r))
        (if (< b 0)
            (progn (ndivmod (- a) b (& r)) (- r))
            (progn (ndivmod (- a) (- b) (& r)) (- r))))))

(defun ndivmod (x y r)
  ;; Division of two negative numbers
  (let ((m 1)
        (q 0))
    (while (>= (+ y y) x)
      (setq y (+ y y))
      (setq m (+ m m)))
    (while (> m 0)
      (when (>= y x)
        (setq q (+ q m))
        (setq x (- x y)))
      (setq y (ash y -1))
      (setq m (shr m)))
    (when r
      (setq (^ r) x))
    q))