(*-*- mode: indented-text; tab-width: 2; -*-*)

MODULE modularInverseInOberon2;

IMPORT Out;

(* Division with a non-negative remainder. This will work no matter
   how your compiler handles DIV (and mine seems not to do what the
   Oberon-2 specification says). *)
PROCEDURE euclidDiv (x, y : INTEGER) : INTEGER;
  VAR q : INTEGER;
BEGIN
  IF 0 <= y THEN      (* Do floor division. *)
    IF 0 <= x THEN
      q := x DIV y
    ELSE
      q := -((-x) DIV y);
      IF (-x) MOD y # 0 THEN q := q - 1 END
    END;
  ELSE                (* Do ceiling division. *)
    IF 0 <= x THEN
      q := -(x DIV (-y))
    ELSE
      q := ((-x) DIV (-y));
      IF (-x) MOD (-y) # 0 THEN q := q + 1 END
    END
  END;
  RETURN q
END euclidDiv;

(* I have added this unit test because, earlier, I posted a buggy
   version of euclidDiv. *)
PROCEDURE testEuclidDiv;
  VAR x, y, q, r : INTEGER;
BEGIN
  FOR x := -100 TO 100 DO
    FOR y := -100 TO 100 DO
      IF y # 0 THEN
        q := euclidDiv (x, y);
        r := x - (q * y);
        IF (r < 0) OR (ABS (y) <= r) THEN
          (* A remainder was outside the expected range. *)
          Out.String ("euclidDiv fails its test")
        END
      END
    END
  END
END testEuclidDiv;

PROCEDURE inverse (a, n : INTEGER) : INTEGER;
  VAR t, newt   : INTEGER;
  VAR r, newr   : INTEGER;
  VAR quotient  : INTEGER;
  VAR tmp       : INTEGER;
BEGIN
  t := 0;  newt := 1;
  r := n;  newr := a;
  WHILE newr # 0 DO
    quotient := euclidDiv (r, newr);
    tmp := newt;  newt := t - (quotient * newt);  t := tmp;
    tmp := newr;  newr := r - (quotient * newr);  r := tmp
  END;
  IF r > 1 THEN
    t := -1
  ELSIF t < 0 THEN
    t := t + n
  END;
  RETURN t
END inverse;

BEGIN
  testEuclidDiv;
  Out.Int (inverse (42, 2017), 0);
  Out.Ln
END modularInverseInOberon2.