39 lines
1.4 KiB
Common Lisp
39 lines
1.4 KiB
Common Lisp
(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)
|