42 lines
1.4 KiB
Text
42 lines
1.4 KiB
Text
%%% -*- mode: mercury; prolog-indent-width: 2; -*-
|
|
%%%
|
|
%%% Compile with:
|
|
%%% mmc --make --use-subdirs modular_inverse_task
|
|
%%%
|
|
|
|
:- module modular_inverse_task.
|
|
:- interface.
|
|
:- import_module io.
|
|
:- pred main(io::di, io::uo) is det.
|
|
|
|
:- implementation.
|
|
:- import_module exception.
|
|
:- import_module int.
|
|
|
|
%% inverse(A, N, Inverse). I assume N > 0, and throw an exception if
|
|
%% it is not. The predicate fails if there is no inverse (and thus is
|
|
%% "semidet"). The algorithm is described at
|
|
%% https://en.wikipedia.org/w/index.php?title=Extended_Euclidean_algorithm&oldid=1135569411#Modular_integers
|
|
:- pred inverse(int::in, int::in, int::out) is semidet.
|
|
inverse(A, N, Inverse) :-
|
|
if (N =< 0) then throw(domain_error("inverse"))
|
|
else inverse_(N, 0, 1, N, A, Inverse).
|
|
|
|
:- pred inverse_(int::in, int::in, int::in, int::in, int::in,
|
|
int::out) is semidet.
|
|
inverse_(N, T, NewT, R, NewR, Inverse) :-
|
|
if (NewR \= 0)
|
|
then (Quotient = div(R, NewR), % Floor division.
|
|
inverse_(N,
|
|
NewT, T - (Quotient * NewT),
|
|
NewR, R - (Quotient * NewR),
|
|
Inverse)) % Tail recursion.
|
|
else (R =< 1, % R =< 1 FAILS if R > 1.
|
|
(if (T < 0) then Inverse = T + N else Inverse = T)).
|
|
|
|
main(!IO) :-
|
|
if inverse(42, 2017, Inverse)
|
|
then (print(Inverse, !IO), nl(!IO))
|
|
else (print("There is no inverse.", !IO), nl(!IO)).
|
|
|
|
:- end_module modular_inverse_task.
|