Modular inverse: Difference between revisions
→{{header|Oberon-2}}
Line 2,189:
1969
</pre>
=={{header|ObjectIcon}}==
{{trans|Oberon-2}}
{{trans|Mercury}}
<syntaxhighlight lang="objecticon">
# -*- ObjectIcon -*-
import exception
import io
procedure main ()
test_euclid_div ()
io.write (inverse (42, 2017))
end
procedure inverse (a, n) # FAILS if there is no inverse.
local t, newt, r, newr, quotient, tmp
if n <= 0 then throw ("non-positive modulus")
t := 0; newt := 1
r := n; newr := a
while newr ~= 0 do
{
quotient := euclid_div (r, newr)
tmp := newt; newt := t - (quotient * newt); t := tmp
tmp := newr; newr := r - (quotient * newr); r := tmp
}
r <= 1 | fail
return (if t < 0 then t + n else t)
end
procedure euclid_div (x, y)
# This kind of integer division always gives a remainder between 0
# and abs(y)-1, inclusive. Thus the remainder is always a LEAST
# RESIDUE modulo abs(y). (If y is a positive modulus, then only the
# floor division branch is used.)
return \
if 0 <= y then # Do floor division.
(if 0 <= x then x / y
else if (-x) % y = 0 then -((-x) / y)
else -((-x) / y) - 1)
else # Do ceiling division.
(if 0 <= x then -(x / (-y))
else if (-x) % (-y) = 0 then ((-x) / (-y))
else ((-x) / (-y)) + 1)
end
procedure test_euclid_div ()
local x, y, q, r
every x := -100 to 100 do
every y := -100 to 100 & y ~= 0 do
{
q := euclid_div (x, y)
r := x - (q * y)
if r < 0 | abs (y) <= r then
# A remainder was outside the expected range.
throw ("Test of euclid_div failed.")
}
end
</syntaxhighlight>
{{out}}
<pre>$ oiscript modular-inverse-task-OI.icn
1969</pre>
=={{header|OCaml}}==
| |||