Modular inverse: Difference between revisions

=={{header|Owl Lisp}}==

{{works with|Owl Lisp|0.2.1}}

''Marginal note'': On Rosetta Code, have Owl Lisp and Ol (Otus Lisp) sometimes been confused with each other? Let it be known, I have written this program for Owl Lisp, not Ol.

<syntaxhighlight lang="scheme">

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

</syntaxhighlight>

{{out}}

<pre>$ ol modular-inverse-task-Owl.scm

1969</pre>