Modular inverse: Difference between revisions
→{{header|AutoHotkey}}
(Modular inverse in BASIC256) |
|||
Line 216:
<pre>1969</pre>
=={{header|ATS}}==
In addition to solving the task, I demonstrate some aspects of call-by-reference in ATS. In particular, ATS can distinguish ''at compile time'' between uninitialized and initialized variables.
<syntaxhighlight lang="ats">
(*
Using the algorithm described at
https://en.wikipedia.org/w/index.php?title=Extended_Euclidean_algorithm&oldid=1135569411#Modular_integers
*)
#include "share/atspre_staload.hats"
fn {tk : tkind}
division_with_nonnegative_remainder
(n : g0int tk, d : g0int tk,
(* q and r are called by reference, and start out
uninitialized. *)
q : &g0int tk? >> g0int tk,
r : &g0int tk? >> g0int tk)
: void =
let
(* The C optimizer most likely will reduce these these two
divisions to just one. They are simply synonyms for C '/' and
'%', and perform division that rounds the quotient towards
zero. *)
val q0 = g0int_div (n, d)
val r0 = g0int_mod (n, d)
in
(* The following calculation results in 'floor division', if the
divisor is positive, or 'ceiling division', if the divisor is
negative. This choice of method results in the remainder never
being negative. *)
if isgtez n || iseqz r0 then
(q := q0; r := r0)
else if isltz d then
(q := succ q0; r := r0 - d)
else
(q := pred q0; r := r0 + d)
end
fn {tk : tkind}
inverse (a : g0int tk, n : g0int tk) : Option_vt (g0int tk) =
let
typedef integer = g0int tk
fun
loop (t : integer, newt : integer,
r : integer, newr : integer) : Option_vt integer =
if iseqz newr then
begin
if r > g0i2i 1 then
None_vt ()
else if t < g0i2i 0 then
Some_vt (t + n)
else
Some_vt t
end
else
let
(* These become C variables. *)
var quotient : g0int tk?
var remainder : g0int tk?
(* Show the type AT COMPILE TIME. *)
prval _ = $showtype quotient
prval _ = $showtype remainder
val () =
division_with_nonnegative_remainder
(r, newr, quotient, remainder)
(* THE TYPES WILL HAVE CHANGED, because the storage is
initialized by the call to
division_with_nonnegative_remainder. *)
prval _ = $showtype quotient
prval _ = $showtype remainder
val t = newt
and newt = t - (quotient * newt)
and r = newr
and newr = remainder
in
loop (t, newt, r, newr)
end
in
loop (g0i2i 0, g0i2i 1, n, a)
end
implement
main0 () =
case+ inverse (42LL, 2017LL) of
| ~ None_vt () => println! "There is no inverse."
| ~ Some_vt value => println! value
</syntaxhighlight>
=={{header|AutoHotkey}}==
| |||