(import (owl math)
        (owl math extra))

(define (euclid-quotient x y)
  (if (<= 0 y)
      (cond ((<= 0 x) (quotient x y))
            ((zero? (remainder (negate x) y))
             (negate (quotient (negate x) y)))
            (else (- (negate (quotient (negate x) y)) 1)))
      (cond ((<= 0 x) (negate (quotient x (negate y))))
            ((zero? (remainder (negate x) (negate y)))
             (quotient (negate x) (negate y)))
            (else (+ (quotient (negate x) (negate y)) 1)))))

;; A unit test of euclid-quotient.
(let repeat ((x -100)
             (y -100))
  (cond ((= x 101) #t)
        ((= y 0) (repeat x (+ y 1)))
        ((= y 101) (repeat (+ x 1) -100))
        (else (let* ((q (euclid-quotient x y))
                     (r (- x (* q y))))
                (cond ((< r 0) (display "negative remainder\n"))
                      ((<= (abs y) r) (display "remainder too large\n"))
                      (else (repeat x (+ y 1))))))))

(define (inverse a n)
  (let repeat ((t 0) (newt 1)
               (r n) (newr a))
    (cond ((not (zero? newr))
           (let ((quotient (euclid-quotient r newr)))
             (repeat newt (- t (* quotient newt))
                     newr (- r (* quotient newr)))))
          ((< 1 r) #f)                  ; The inverse does not exist.
          ((negative? t) (+ t n))
          (else t))))

(display (inverse 42 2017))
(newline)