%%% -*- 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.