75 lines
1.8 KiB
Text
75 lines
1.8 KiB
Text
(*-*- 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.
|