Modular inverse: Difference between revisions
m
→{{header|Wren}}: Minor tidy
Not a robot (talk | contribs) (Add BCPL) |
m (→{{header|Wren}}: Minor tidy) |
||
| (46 intermediate revisions by 17 users not shown) | |||
Line 22:
{{trans|C}}
<
V b0 = b
V x0 = 0
Line 36:
R x1
print(mul_inv(42, 2017))</
{{out}}
Line 44:
=={{header|8th}}==
<syntaxhighlight lang="forth">
\ return "extended gcd" of a and b; The result satisfies the equation:
\ a*x + b*y = gcd(a,b)
Line 69:
42 2017 n:invmod . cr bye
</syntaxhighlight>
{{out}}
<pre>
Line 76:
=={{header|Action!}}==
<
INT t,nt,r,nr,q,tmp
Line 114:
Test(-486,217)
Test(40,2018)
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Modular_inverse.png Screenshot from Atari 8-bit computer]
Line 127:
=={{header|Ada}}==
<syntaxhighlight lang="ada">
with Ada.Text_IO;use Ada.Text_IO;
procedure modular_inverse is
Line 147:
exception when others => Put_Line ("The inverse doesn't exist.");
end modular_inverse;
</syntaxhighlight>
=={{header|ALGOL 68}}==
<
BEGIN
PROC modular inverse = (INT a, m) INT :
Line 186:
CO
END
</syntaxhighlight>
{{out}}
<pre>42 ^ -1 (mod 2017) = 1969
Line 195:
{{trans|D}}
<
if b = 1 -> return 1
Line 211:
]
print modInverse 42 2017</
{{out}}
<pre>1969</pre>
=={{header|ATS}}==
===Using allocated memory===
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.
The code is written as templates that will expand to code for any of the (non-dependent) signed integer types. In the main program, I use <code>llint</code> (typically exactly the same as <code>long long int</code> in C).
The return value of <code>inverse</code> is a linear optional value. It is allocated in the heap, used once, and freed.
<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>
{{out}}
First compile the program:
<pre>$ patscc -DATS_MEMALLOC_LIBC -g -O2 modular-inverse.dats
**SHOWTYPE[UP]**(/home/trashman/src/chemoelectric/rosettacode-contributions/modular-inverse.dats: 1786(line=62, offs=31) -- 1794(line=62, offs=39)): S2Etop(knd=0; S2Eapp(S2Ecst(g0int_t0ype); S2Evar(tk(8481)))): S2RTbas(S2RTBASimp(1; t@ype))
**SHOWTYPE[UP]**(/home/trashman/src/chemoelectric/rosettacode-contributions/modular-inverse.dats: 1825(line=63, offs=31) -- 1834(line=63, offs=40)): S2Etop(knd=0; S2Eapp(S2Ecst(g0int_t0ype); S2Evar(tk(8481)))): S2RTbas(S2RTBASimp(1; t@ype))
**SHOWTYPE[UP]**(/home/trashman/src/chemoelectric/rosettacode-contributions/modular-inverse.dats: 2137(line=72, offs=31) -- 2145(line=72, offs=39)): S2Eapp(S2Ecst(g0int_t0ype); S2Evar(tk(8481))): S2RTbas(S2RTBASimp(1; t@ype))
**SHOWTYPE[UP]**(/home/trashman/src/chemoelectric/rosettacode-contributions/modular-inverse.dats: 2176(line=73, offs=31) -- 2185(line=73, offs=40)): S2Eapp(S2Ecst(g0int_t0ype); S2Evar(tk(8481))): S2RTbas(S2RTBASimp(1; t@ype))
</pre>
You may notice there is a subtle change in the type of <code>quotient</code> and <code>remainder</code>, once they have been initialized. ATS is making it safe ''not'' to initialize variables (with phony values) when you declare them.
Now run the program:
<pre>$ ./a.out
1969</pre>
===Safely avoiding the need for an allocator===
Here I demonstrate an optional value that requires no runtime overhead at all, but which is safe. If there is no inverse, then the compiler knows that <code>inverse_value</code> is still uninitialized, and will not let you use its value. (Try it and see.)
<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,
inverse_exists : &bool? >> bool exists,
inverse_value : &g0int tk? >> opt (g0int tk, exists))
: #[exists: bool] void =
let
typedef integer = g0int tk
fun
loop (t : integer, newt : integer,
r : integer, newr : integer,
inverse_exists : &bool? >> bool exists,
inverse_value : &g0int tk? >> opt (g0int tk, exists))
: #[exists: bool] void =
if iseqz newr then
begin
if r > g0i2i 1 then
let
val () = inverse_exists := false
prval () = opt_none inverse_value
in
end
else if t < g0i2i 0 then
let
val () = inverse_exists := true
val () = inverse_value := t + n
prval () = opt_some inverse_value
in
end
else
let
val () = inverse_exists := true
val () = inverse_value := t
prval () = opt_some inverse_value
in
end
end
else
let
(* These become C variables. *)
var quotient : g0int tk?
var remainder : g0int tk?
val () =
division_with_nonnegative_remainder
(r, newr, quotient, remainder)
val t = newt
and newt = t - (quotient * newt)
and r = newr
and newr = remainder
in
loop (t, newt, r, newr, inverse_exists, inverse_value)
end
in
loop (g0i2i 0, g0i2i 1, n, a, inverse_exists, inverse_value)
end
implement
main0 () =
let
var inverse_exists : bool?
var inverse_value : llint?
in
inverse (42LL, 2017LL, inverse_exists, inverse_value);
if inverse_exists then
let
prval () = opt_unsome inverse_value
in
println! inverse_value
end
else
let
prval () = opt_unnone inverse_value
in
println! "There is no inverse."
end
end
</syntaxhighlight>
{{out}}
There is no need to tell patscc what allocator to use, because none is used.
<pre>$ patscc -g -O2 modular-inverse-noheap.dats && ./a.out
1969</pre>
=={{header|AutoHotkey}}==
Translation of [http://rosettacode.org/wiki/Modular_inverse#C C].
<
ModInv(a, b) {
Line 237 ⟶ 481:
x1 += b0
return x1
}</
{{out}}
<pre>1969</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f MODULAR_INVERSE.AWK
# converted from C
Line 270 ⟶ 514:
return(x1)
}
</syntaxhighlight>
{{out}}
<pre>
Line 279 ⟶ 523:
==={{header|ASIC}}===
{{trans|Pascal}}
<
REM Modular inverse
E = 42
Line 289 ⟶ 533:
CalcModInv:
REM Increments E Step times until Bal is greater than T
REM Repeats until Bal = 1 (MOD = 1) and returns Count
REM Bal will not be greater than T + E
D = 0
Line 309 ⟶ 553:
ModInv = D
RETURN
</syntaxhighlight>
{{out}}
<pre>
1969
</pre>
==={{header|BASIC256}}===
<syntaxhighlight lang="basic">print multInv(42, 2017)
end
function multInv(a,b)
x0 = 0
b0 = b
multInv = 1
if b = 1 then return
while a > 1
q = a / b
t = b
b = a mod b
a = t
t = x0
x0 = multInv - q * x0
multInv = int(t)
end while
if multInv < 0 then return multInv + b0
end function</syntaxhighlight>
{{out}}
<pre>1969</pre>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{works with|QBasic}}
{{trans|BASIC256}}
<syntaxhighlight lang="qbasic">10 CLS
20 CALL modularinverse(42, 2017)
30 CALL modularinverse(40, 1)
40 END
50 SUB modularinverse(e,t)
60 d = 0
70 IF e < t THEN
80 b = e
90 c = 1
100 WHILE b > 1
110 s = INT(((t-b)/e)+1)
120 b = b+s*e
130 c = c+s
140 b = b-t
150 WEND
160 d = c
170 ENDIF
180 m = d
190 PRINT m
200 END SUB</syntaxhighlight>
==={{header|Minimal BASIC}}===
{{trans|Pascal}}
{{works with|Applesoft BASIC}}
{{works with|Commodore BASIC|3.5}}
{{works with|Nascom ROM BASIC|4.7}}
<syntaxhighlight lang="gwbasic">
10 REM Modular inverse
20 LET E = 42
30 LET T = 2017
40 GOSUB 500
50 PRINT M
60 END
490 REM Calculate modular inverse
500 LET D = 0
510 IF E >= T THEN 600
520 LET B = E
530 LET C = 1
540 LET S1 = INT((T-B)/E)+1
550 LET B = B+S1*E
560 LET C = C+S1
570 LET B = B-T
580 IF B <> 1 THEN 540
590 LET D = C
600 LET M = D
610 RETURN
</syntaxhighlight>
==={{header|QBasic}}===
The [[#Chipmunk_Basic|Chipmunk Basic]] solution works without any changes.
<syntaxhighlight lang="qbasic"></syntaxhighlight>
==={{header|True BASIC}}===
<syntaxhighlight lang="qbasic">SUB modularinverse(e,t)
LET d = 0
IF e < t then
LET b = e
LET c = 1
DO WHILE b > 1
LET s = int(((t-b)/e)+1)
LET b = b+s*e
LET c = c+s
LET b = b-t
LOOP
LET d = c
END IF
LET m = d
PRINT m
END SUB
CALL modularinverse(42,2017)
CALL modularinverse(40,1)
END</syntaxhighlight>
=={{header|Batch File}}==
Line 319 ⟶ 664:
{{trans|Perl}}
<
setlocal enabledelayedexpansion
%== Calls the "function" ==%
Line 361 ⟶ 706:
if !t! lss 0 set /a t+=b
set %3=!t!
goto :EOF</
{{Out}}
<pre>1969
Line 370 ⟶ 715:
=={{header|BCPL}}==
<
let mulinv(a, b) =
Line 400 ⟶ 745:
show(-486, 217)
show(40, 2018)
$)</
{{out}}
<pre>42, 2017 -> 1969
Line 410 ⟶ 755:
=={{header|Bracmat}}==
{{trans|Julia}}
<
= a b b0 x0 x1 q
. !arg:(?a.?b)
Line 425 ⟶ 770:
)
& out$(mod-inv$(42.2017))
};</
Output
<pre>1969</pre>
=={{header|C}}==
<
int mul_inv(int a, int b)
Line 449 ⟶ 794:
printf("%d\n", mul_inv(42, 2017));
return 0;
}</
The above method has some problems. Most importantly, when given a pair (a,b) with no solution, it generates an FP exception. When given <tt>b=1</tt>, it returns 1 which is not a valid result mod 1. When given negative a or b the results are incorrect. The following generates results that should match Pari/GP for numbers in the int range.
{{trans|Perl}}
<
int mul_inv(int a, int b)
Line 477 ⟶ 822:
printf("%d\n", mul_inv(40, 2018));
return 0;
}</
{{out}}
<pre>
Line 488 ⟶ 833:
=={{header|C sharp}}==
<
{
static void Main()
Line 511 ⟶ 856:
return x < 0 ? x + m0 : x;
}
}</
=={{header|C++}}==
===Iterative implementation===
{{trans|C}}
<
int mul_inv(int a, int b)
Line 535 ⟶ 880:
std::cout << mul_inv(42, 2017) << std::endl;
return 0;
}</
===Recursive implementation===
<
short ObtainMultiplicativeInverse(int a, int b, int s0 = 1, int s1 = 0)
Line 549 ⟶ 894:
std::cout << ObtainMultiplicativeInverse(42, 2017) << std::endl;
return 0;
}</
=={{header|Clojure}}==
<
(:require [clojure.math.numeric-tower :as math]))
Line 596 ⟶ 941:
(println (mul_inv 40 2018))
</syntaxhighlight>
'''Output:'''
Line 609 ⟶ 954:
=={{header|CLU}}==
{{trans|Perl}}
<
if b<0 then b := -b end
if a<0 then a := b - (-a // b) end
Line 644 ⟶ 989:
end
end
end start_up</
{{out}}
<pre>42, 2017 -> 1969
Line 651 ⟶ 996:
-486, 217 -> 121
40, 2018 -> no modular inverse</pre>
=={{header|Comal}}==
<syntaxhighlight lang="comal">0010 FUNC mulinv#(a#,b#) CLOSED
0020 IF b#<0 THEN b#:=-b#
0030 IF a#<0 THEN a#:=b#-(-a# MOD b#)
0040 t#:=0;nt#:=1;r#:=b#;nr#:=a# MOD b#
0050 WHILE nr#<>0 DO
0060 q#:=r# DIV nr#
0070 tmp#:=nt#;nt#:=t#-q#*nt#;t#:=tmp#
0080 tmp#:=nr#;nr#:=r#-q#*nr#;r#:=tmp#
0090 ENDWHILE
0100 IF r#>1 THEN RETURN -1
0110 IF t#<0 THEN t#:+b#
0120 RETURN t#
0130 ENDFUNC mulinv#
0140 //
0150 WHILE NOT EOD DO
0160 READ a#,b#
0170 PRINT a#,", ",b#," -> ",mulinv#(a#,b#)
0180 ENDWHILE
0190 END
0200 //
0210 DATA 42,2017,40,1,52,-217,-486,217,40,2018</syntaxhighlight>
{{out}}
<pre>42, 2017 -> 1969
40, 1 -> 0
52, -217 -> 96
-486, 217 -> 121
40, 2018 -> -1</pre>
=={{header|Common Lisp}}==
<
;;
;; Calculates the GCD of a and b based on the Extended Euclidean Algorithm. The function also returns
Line 677 ⟶ 1,051:
(unless (= 1 r) (error "invmod: Values ~a and ~a are not coprimes." a m))
s))
</syntaxhighlight>
{{out}}
Line 688 ⟶ 1,062:
1969
</pre>
=={{header|Cowgol}}==
<syntaxhighlight lang="cowgol">include "cowgol.coh";
sub mulinv(a: int32, b: int32): (t: int32) is
if b<0 then b := -b; end if;
if a<0 then a := b - (-a % b); end if;
t := 0;
var nt: int32 := 1;
var r := b;
var nr := a % b;
while nr != 0 loop
var q := r / nr;
var tmp := nt; nt := t - q*nt; t := tmp;
tmp := nr; nr := r - q*nr; r := tmp;
end loop;
if r>1 then t := -1;
elseif t<0 then t := t + b;
end if;
end sub;
record Pair is
a: int32;
b: int32;
end record;
var data: Pair[] := {
{42, 2017},
{40, 1},
{52, -217},
{-486, 217},
{40, 2018}
};
var i: @indexof data := 0;
while i < @sizeof data loop
print_i32(data[i].a as uint32);
print(", ");
print_i32(data[i].b as uint32);
print(" -> ");
var mi := mulinv(data[i].a, data[i].b);
if mi<0
then print("no inverse");
else print_i32(mi as uint32);
end if;
print_nl();
i := i + 1;
end loop;</syntaxhighlight>
{{out}}
<pre>42, 2017 -> 1969
40, 1 -> 0
52, 4294967079 -> 96
4294966810, 217 -> 121
40, 2018 -> no inverse</pre>
=={{header|Craft Basic}}==
<syntaxhighlight lang="basic">let e = 42
let t = 2017
gosub modularinverse
end
sub modularinverse
let d = 0
if e < t then
let b = e
let c = 1
do
let s = int(((t - b) / e) + 1)
let b = b + s * e
let c = c + s
let b = b - t
loop b <> 1
let d = c
endif
let m = d
print m
return</syntaxhighlight>
{{out| Output}}<pre>1969</pre>
=={{header|Crystal}}==
{{trans|Ruby}}
<
return 1 if m0 == 1
a, m = a0, m0
Line 702 ⟶ 1,167:
inv += m0 if inv < 0
inv
end</
{{out}}
Line 711 ⟶ 1,176:
=={{header|D}}==
{{trans|C}}
<
if (b == 1)
return 1;
Line 733 ⟶ 1,198:
import std.stdio;
writeln(modInverse(42, 2017));
}</
{{out}}
<pre>1969</pre>
Line 739 ⟶ 1,204:
{{trans|C}}
This solution prints the inverse <code>u</code> only if it exists (<code>a*u = 1 mod m</code>).
<syntaxhighlight lang="dc">
dc -e "[m=]P?dsm[a=]P?dsa1sv[dsb~rsqlbrldlqlv*-lvsdsvd0<x]dsxxldd[dlmr+]sx0>xdla*lm%[p]sx1=x"
</syntaxhighlight>
If <code>~</code> is not implemented, it can be replaced by <code>SdSnlnld/LnLd%</code>.
Line 767 ⟶ 1,232:
=={{header|Delphi}}==
See [[#Pascal]].
=={{header|Draco}}==
<syntaxhighlight lang="draco">proc mulinv(int a, b) int:
int t, nt, r, nr, q, tmp;
if b<0 then b := -b fi;
if a<0 then a := b - (-a % b) fi;
t := 0; nt := 1; r := b; nr := a % b;
while nr /= 0 do
q := r / nr;
tmp := nt; nt := t - q*nt; t := tmp;
tmp := nr; nr := r - q*nr; r := tmp
od;
if r>1 then -1
elif t<0 then t+b
else t
fi
corp
proc show(int a, b) void:
int mi;
mi := mulinv(a, b);
if mi>=0
then writeln(a:5, ", ", b:5, " -> ", mi:5)
else writeln(a:5, ", ", b:5, " -> no inverse")
fi
corp
proc main() void:
show(42, 2017);
show(40, 1);
show(52, -217);
show(-486, 217);
show(40, 2018)
corp</syntaxhighlight>
{{out}}
<pre> 42, 2017 -> 1969
40, 1 -> 0
52, -217 -> 96
-486, 217 -> 121
40, 2018 -> no inverse</pre>
=={{header|EasyLang}}==
{{trans|AWK}}
<syntaxhighlight lang="easylang">
func mod_inv a b .
b0 = b
x1 = 1
if b = 1
return 1
.
while a > 1
q = a div b
t = b
b = a mod b
a = t
t = x0
x0 = x1 - q * x0
x1 = t
.
if x1 < 0
x1 += b0
.
return x1
.
print mod_inv 42 2017
</syntaxhighlight>
=={{header|EchoLisp}}==
<
(lib 'math) ;; for egcd = extended gcd
Line 780 ⟶ 1,311:
(mod-inv 42 666)
🔴 error: not-coprimes (42 666)
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Ruby}}
<
def extended_gcd(a, b) do
{last_remainder, last_x} = extended_gcd(abs(a), abs(b), 1, 0, 0, 1)
Line 804 ⟶ 1,335:
end
IO.puts Modular.inverse(42,2017)</
{{out}}
Line 812 ⟶ 1,343:
=={{header|ERRE}}==
<
!$INTEGER
Line 838 ⟶ 1,369:
MUL_INV(40,2018->T) PRINT(T)
END PROGRAM
</syntaxhighlight>
{{out}}
<pre>
Line 849 ⟶ 1,380:
=={{header|F_Sharp|F#}}==
<
// Calculate the inverse of a (mod m)
// See here for eea specs:
Line 861 ⟶ 1,392:
eea t' (t - div * t') r' (r - div * r')
(m + eea 0 1 m a) % m
</syntaxhighlight>
{{in}}
<pre>
Line 873 ⟶ 1,404:
=={{header|Factor}}==
<syntaxhighlight lang="text">USE: math.functions
42 2017 mod-inv</
{{out}}
<pre>
Line 882 ⟶ 1,413:
=={{header|Forth}}==
ANS Forth with double-number word set
<
: invmod { a m | v b c -- inv }
m to v
Line 893 ⟶ 1,424:
repeat b m mod dup to b 0<
if m b + else b then ;
</syntaxhighlight>
ANS Forth version without locals
<
: modinv ( a m - inv)
dup 1- \ a m (m != 1)?
Line 914 ⟶ 1,445:
nip \ inv
;
</syntaxhighlight>
<pre>
42 2017 invmod . 1969
42 2017 modinv . 1969
</pre>
=={{header|Fortran}}==
<syntaxhighlight lang="fortran">
program modular_inverse_task
implicit none
write (*,*) inverse (42, 2017)
contains
! Returns -1 if there is no inverse. I assume n > 0. The algorithm
! is described at
! https://en.wikipedia.org/w/index.php?title=Extended_Euclidean_algorithm&oldid=1135569411#Modular_integers
function inverse (a, n) result (inverse_value)
integer, intent(in) :: a, n
integer :: inverse_value
integer :: t, newt
integer :: r, newr
integer :: quotient, remainder, tmp
if (n <= 0) error stop
t = 0; newt = 1
r = n; newr = a
do while (newr /= 0)
remainder = modulo (r, newr) ! Floor division.
quotient = (r - remainder) / newr
tmp = newt; newt = t - (quotient * newt); t = tmp
r = newr; newr = remainder
end do
if (r > 1) then
inverse_value = -1
else if (t < 0) then
inverse_value = t + n
else
inverse_value = t
end if
end function inverse
end program modular_inverse_task
</syntaxhighlight>
{{out}}
<pre>$ gfortran -Wall -Wextra modular_inverse_task.f90 && ./a.out
1969
</pre>
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 995 ⟶ 1,573:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>a * 42 + b * 2017 = GCD(42, 2017) = 1
Line 1,017 ⟶ 1,595:
=={{header|Frink}}==
<syntaxhighlight lang
{{out}}
<pre>
Line 1,024 ⟶ 1,602:
=={{header|FunL}}==
<
def modinv( a, m ) =
Line 1,035 ⟶ 1,613:
if res < 0 then res + m else res
println( modinv(42, 2017) )</
{{out}}
Line 1,045 ⟶ 1,623:
=={{header|Go}}==
The standard library function uses the extended Euclidean algorithm internally.
<
import (
Line 1,057 ⟶ 1,635:
k := new(big.Int).ModInverse(a, m)
fmt.Println(k)
}</
{{out}}
<pre>
Line 1,066 ⟶ 1,644:
{{trans|Pascal}}
{{works with|PC-BASIC|any}}
<
10 ' Modular inverse
20 LET E% = 42
Line 1,094 ⟶ 1,672:
1140 LET MODINV% = D%
1150 RETURN
</syntaxhighlight>
{{out}}
<pre>
Line 1,101 ⟶ 1,679:
=={{header|Haskell}}==
<
-- If there is no such x return Nothing.
modInv :: Int -> Int -> Maybe Int
Line 1,125 ⟶ 1,703:
main :: IO ()
main = mapM_ print [2 `modInv` 4, 42 `modInv` 2017]</
{{out}}
<pre>Nothing
Line 1,132 ⟶ 1,710:
=={{header|Icon}} and {{header|Unicon}}==
{{trans|C}}
<
a := integer(args[1]) | 42
b := integer(args[2]) | 2017
Line 1,147 ⟶ 1,725:
}
return if (x1 > 0) then x1 else x1+b0
end</
{{out}}
Line 1,158 ⟶ 1,736:
Adding a coprime test:
<
procedure main(args)
Line 1,176 ⟶ 1,754:
}
return if (x1 > 0) then x1 else x1+b0
end</
=={{header|IS-BASIC}}==
<
120 DEF MODINV(A,B)
130 LET B=ABS(B)
Line 1,196 ⟶ 1,774:
260 LET MODINV=T
270 END IF
280 END DEF</
=={{header|J}}==
'''Solution''':<
'''Example''':<
1969</
'''Notes''':
Line 1,212 ⟶ 1,790:
=={{header|Java}}==
The <code>BigInteger</code> library has a method for this:
<
{{out}}
<pre>1969</pre>
Alternatively, working from first principles.
<syntaxhighlight lang="java">
public final class ModularInverse {
public static void main(String[] aArgs) {
System.out.println(inverseModulus(42, 2017));
}
private static Egcd extendedGCD(int aOne, int aTwo) {
if ( aOne == 0 ) {
return new Egcd(aTwo, 0, 1);
}
Egcd value = extendedGCD(aTwo % aOne, aOne);
return new Egcd(value.aG, value.aY - ( aTwo / aOne ) * value.aX, value.aX);
}
private static int inverseModulus(int aNumber, int aModulus) {
Egcd value = extendedGCD(aNumber, aModulus);
return ( value.aG == 1 ) ? ( value.aX + aModulus ) % aModulus : 0;
}
private static record Egcd(int aG, int aX, int aY) {}
}
</syntaxhighlight>
{{ out }}
<pre>
1969
</pre>
=={{header|JavaScript}}==
Using brute force.
<
a %= b;
for (var x = 1; x < b; x++) {
Line 1,225 ⟶ 1,832:
}
}
}</
=={{header|jq}}==
Line 1,231 ⟶ 1,838:
'''Works with gojq, the Go implementation of jq'''
<
# If $j is 0, then an error condition is raised;
# otherwise, assuming infinite-precision integer arithmetic,
Line 1,267 ⟶ 1,874:
# Example:
42 | modInv(2017)
</syntaxhighlight>
{{out}}
<pre>
Line 1,278 ⟶ 1,885:
===Built-in===
Julia includes a built-in function for this:
<syntaxhighlight lang
===C translation===
Line 1,284 ⟶ 1,891:
The following code works on any integer type.
To maximize performance, we ensure (via a promotion rule) that the operands are the same type (and use built-ins <code>zero(T)</code> and <code>one(T)</code> for initialization of temporary variables to ensure that they remain of the same type throughout execution).
<
b0 = b
x0, x1 = zero(T), one(T)
Line 1,294 ⟶ 1,901:
x1 < 0 ? x1 + b0 : x1
end
modinv(a::Integer, b::Integer) = modinv(promote(a,b)...)</
{{out}}
Line 1,306 ⟶ 1,913:
=={{header|Kotlin}}==
<
import java.math.BigInteger
Line 1,314 ⟶ 1,921:
val m = BigInteger.valueOf(2017)
println(a.modInverse(m))
}</
{{out}}
Line 1,320 ⟶ 1,927:
1969
</pre>
=={{header|Lambdatalk}}==
{{trans|Phix}}
<syntaxhighlight lang="scheme">
{def mulinv
{def mulinv.loop
{lambda {:t :nt :r :nr}
{if {not {= :nr 0}}
then {mulinv.loop :nt
{- :t {* {floor {/ :r :nr}} :nt}}
:nr
{- :r {* {floor {/ :r :nr}} :nr}} }
else {cons :t :r} }}}
{lambda {:a :n}
{let { {:a :a} {:n :n}
{:cons {mulinv.loop 0
1
{if {< :n 0} then {- :n} else :n}
{if {< :a 0} then {- :n {% {- :a} :n}} else :a}}}
} {if {> {cdr :cons} 1}
then not invertible
else {if {< {car :cons} 0}
then {+ {car :cons} :n}
else {car :cons} }}}}}
-> mulinv
{mulinv 42 2017}
-> 1969
{mulinv 40 1}
-> 0
{mulinv 52 -217}
-> 96
{mulinv -486 217}
-> 121
{mulinv 40 218}
-> not invertible
</syntaxhighlight>
=={{header|m4}}==
{{trans|Mercury}}
Note that <code>$0</code> is the name of the macro being evaluated. Therefore, in the following, <code>_$0</code> is the name of another macro, the same as the name of the first macro, except for an underscore prepended. This is a common idiom.
The core of the program is <code>__inverse</code> recursively calling itself.
m4 is a macro-preprocessor, and so some of the following is there simply to keep things from being echoed to the output. :)
<syntaxhighlight lang="m4">
divert(-1)
# I assume non-negative arguments. The algorithm is described at
# https://en.wikipedia.org/w/index.php?title=Extended_Euclidean_algorithm&oldid=1135569411#Modular_integers
define(`inverse',`_$0(eval(`$1'), eval(`$2'))')
define(`_inverse',`_$0($2, 0, 1, $2, $1)')
define(`__inverse',
`dnl n = $1, t = $2, newt = $3, r = $4, newr = $5
ifelse(eval($5 != 0), 1, `$0($1, $3,
eval($2 - (($4 / $5) * $3)),
$5,eval($4 % $5))',
eval($4 > 1), 1, `no inverse',
eval($2 < 0), 1, eval($2 + $1),
$2)')
divert`'dnl
inverse(42, 2017)
</syntaxhighlight>
{{out}}
<pre>$ m4 modular-inverse-task.m4
1969</pre>
=={{header|MAD}}==
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER
INTERNAL FUNCTION(AA, BB)
ENTRY TO MULINV.
A = AA
B = BB
WHENEVER B.L.0, B = -B
WHENEVER A.L.0, A = B - (-(A-A/B*B))
T = 0
NT = 1
R = B
NR = A-A/B*B
LOOP WHENEVER NR.NE.0
Q = R/NR
TMP = NT
NT = T - Q*NT
T = TMP
TMP = NR
NR = R - Q*NR
R = TMP
TRANSFER TO LOOP
END OF CONDITIONAL
WHENEVER R.G.1, FUNCTION RETURN -1
WHENEVER T.L.0, T = T+B
FUNCTION RETURN T
END OF FUNCTION
INTERNAL FUNCTION(AA, BB)
VECTOR VALUES FMT = $I5,2H, ,I5,2H: ,I5*$
ENTRY TO SHOW.
PRINT FORMAT FMT, AA, BB, MULINV.(AA, BB)
END OF FUNCTION
SHOW.(42,2017)
SHOW.(40,1)
SHOW.(52,-217)
SHOW.(-486,217)
SHOW.(40,2018)
END OF PROGRAM</syntaxhighlight>
{{out}}
<pre> 42, 2017: 1969
40, 1: 0
52, -217: 96
-486, 217: 121
40, 2018: -1</pre>
=={{header|Maple}}==
<syntaxhighlight lang="maple">
1/42 mod 2017;
</syntaxhighlight>
{{out}}
<pre>
Line 1,332 ⟶ 2,058:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ModularInverse[a, m]</syntaxhighlight>
For example:
<pre>ModularInverse[42, 2017]
1969</pre>
=={{header|Maxima}}==
Using built-in function inv_mod
<syntaxhighlight lang="maxima">
inv_mod(42,2017);
</syntaxhighlight>
{{out}}
<pre>
1969
</pre>
=={{header|Mercury}}==
{{works with|Mercury|22.01.1}}
<syntaxhighlight lang="mercury">
%%% -*- 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.
</syntaxhighlight>
{{out}}
<pre>$ mmc --make --use-subdirs modular_inverse_task && ./modular_inverse_task
Making Mercury/int3s/modular_inverse_task.int3
Making Mercury/ints/modular_inverse_task.int
Making Mercury/cs/modular_inverse_task.c
Making Mercury/os/modular_inverse_task.o
Making modular_inverse_task
1969
</pre>
=={{header|МК-61/52}}==
<syntaxhighlight lang="text">П1 П2 <-> П0 0 П5 1 П6 ИП1 1
- x=0 14 С/П ИП0 1 - /-/ x<0 50
ИП0 ИП1 / [x] П4 ИП1 П3 ИП0 ^ ИП1
/ [x] ИП1 * - П1 ИП3 П0 ИП5 П3
ИП6 ИП4 ИП5 * - П5 ИП3 П6 БП 14
ИП6 x<0 55 ИП2 + С/П</
=={{header|Modula-2}}==
{{trans|C}}
<
FROM InOut IMPORT WriteString, WriteInt, WriteLn;
Line 1,396 ⟶ 2,185:
WriteLn;
END;
END ModularInverse.</
{{out}}
<pre>Modular inverse
Line 1,406 ⟶ 2,195:
=={{header|newLISP}}==
<syntaxhighlight lang="newlisp">
(define (modular-multiplicative-inverse a n)
(if (< n 0)
Line 1,437 ⟶ 2,226:
(println (modular-multiplicative-inverse 42 2017))
</syntaxhighlight>
Output:
Line 1,446 ⟶ 2,235:
=={{header|Nim}}==
{{trans|C}}
<
var (a, b, x0) = (a0, b0, 0)
result = 1
Line 1,457 ⟶ 2,246:
if result < 0: result += b0
echo modInv(42, 2017)</
{{out}}
<pre>1969</pre>
=={{header|Oberon-2}}==
{{works with|Oxford Oberon-2 Compiler|3.3.0}}
<syntaxhighlight lang="oberon">
(*-*- 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.
</syntaxhighlight>
{{out}}
<pre>$ obc modularInverseInOberon2.Mod && ./a.out
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}}==
==={{trans|C}}===
<
let rec aux a b x0 x1 =
if a <= 1 then x1 else
Line 1,472 ⟶ 2,413:
in
let x = aux a b 0 1 in
if x < 0 then x + b else x</
Testing:
Line 1,482 ⟶ 2,423:
==={{trans|Haskell}}===
<
| 0 -> (1, 0, a)
| b ->
Line 1,492 ⟶ 2,433:
match gcd_ext a m with
| i, _, 1 -> mk_pos i
| _ -> failwith "mod_inv"</
Testing:
Line 1,504 ⟶ 2,445:
Usage : a modulus invmod
<
// Return r = gcd(a, b) and (u, v) / r = au + bv
Line 1,525 ⟶ 2,466:
: invmod(a, modulus)
a modulus euclid 1 == ifFalse: [ drop drop null return ]
drop dup 0 < ifTrue: [ modulus + ] ;</
{{out}}
Line 1,532 ⟶ 2,473:
1969
</pre>
=={{header|Owl Lisp}}==
{{works with|Owl Lisp|0.2.1}}
<syntaxhighlight lang="scheme">
(import (owl math)
(owl math extra))
(define (euclid-quotient x y)
(if (<= 0 y)
(cond ((<= 0 x) (quotient x y))
((zero? (remainder (negate x) y))
(negate (quotient (negate x) y)))
(else (- (negate (quotient (negate x) y)) 1)))
(cond ((<= 0 x) (negate (quotient x (negate y))))
((zero? (remainder (negate x) (negate y)))
(quotient (negate x) (negate y)))
(else (+ (quotient (negate x) (negate y)) 1)))))
;; A unit test of euclid-quotient.
(let repeat ((x -100)
(y -100))
(cond ((= x 101) #t)
((= y 0) (repeat x (+ y 1)))
((= y 101) (repeat (+ x 1) -100))
(else (let* ((q (euclid-quotient x y))
(r (- x (* q y))))
(cond ((< r 0) (display "negative remainder\n"))
((<= (abs y) r) (display "remainder too large\n"))
(else (repeat x (+ y 1))))))))
(define (inverse a n)
(let repeat ((t 0) (newt 1)
(r n) (newr a))
(cond ((not (zero? newr))
(let ((quotient (euclid-quotient r newr)))
(repeat newt (- t (* quotient newt))
newr (- r (* quotient newr)))))
((< 1 r) #f) ; The inverse does not exist.
((negative? t) (+ t n))
(else t))))
(display (inverse 42 2017))
(newline)
</syntaxhighlight>
{{out}}
<pre>$ ol modular-inverse-task-Owl.scm
1969</pre>
=={{header|PARI/GP}}==
<syntaxhighlight lang
=={{header|Pascal}}==
<syntaxhighlight lang="pascal">
// increments e step times until bal is greater than t
// repeats until bal = 1 (mod = 1) and returns count
Line 1,561 ⟶ 2,551:
end;
modInv := d;
end;</
Testing:
Line 1,572 ⟶ 2,562:
=={{header|Perl}}==
Various CPAN modules can do this, such as:
<
# or
use Math::ModInt qw/mod/; say mod(42, 2017)->inverse->residue;
Line 1,580 ⟶ 2,570:
use Math::GMP qw/:constant/; say 42->bmodinv(2017);
# or
use ntheory qw/invmod/; say invmod(42, 2017);</
or we can write our own:
<
my($a,$n) = @_;
my($t,$nt,$r,$nr) = (0, 1, $n, $a % $n);
Line 1,596 ⟶ 2,586:
}
say invmod(42,2017);</
'''Notes''': Special cases to watch out for include (1) where the inverse doesn't exist, such as invmod(14,28474), which should return undef or raise an exception, not return a wrong value. (2) the high bit of a or n is set, e.g. invmod(11,2**63), (3) negative first arguments, e.g. invmod(-11,23).
The modules and code above handle these cases,
Line 1,603 ⟶ 2,593:
=={{header|Phix}}==
{{trans|C}}
<!--<
<span style="color: #008080;">function</span> <span style="color: #000000;">mul_inv</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">n</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
Line 1,624 ⟶ 2,614:
<span style="color: #0000FF;">?</span><span style="color: #000000;">mul_inv</span><span style="color: #0000FF;">(-</span><span style="color: #000000;">486</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">217</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">mul_inv</span><span style="color: #0000FF;">(</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2018</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 1,636 ⟶ 2,626:
=={{header|PHP}}==
'''Algorithm Implementation'''
<
function invmod($a,$n){
if ($n < 0) $n = -$n;
Line 1,651 ⟶ 2,641:
}
printf("%d\n", invmod(42, 2017));
?></
{{Out}}
<pre>1969</pre>
Line 1,657 ⟶ 2,647:
=={{header|PicoLisp}}==
{{trans|C}}
<
(let (B0 B X0 0 X1 1 Q 0 T1 0)
(while (< 1 A)
Line 1,673 ⟶ 2,663:
(modinv 42 2017) )
(bye)</
=={{header|PL/I}}==
{{trans|REXX}}
<
/*--------------------------------------------------------------------
* 13.07.2015 Walter Pachl
Line 1,709 ⟶ 2,699:
Return(d);
End;
End;</
{{out}}
<pre>modular inverse of 42 by 2017 ---> 1969</pre>
=={{header|PowerShell}}==
<
if ([int]$n -lt 0) {$n = -$n}
if ([int]$a -lt 0) {$a = $n - ((-$a) % $n)}
Line 1,736 ⟶ 2,726:
}
invmod 42 2017</
{{Out}}
<pre>PS> .\INVMOD.PS1
Line 1,743 ⟶ 2,733:
=={{header|Prolog}}==
<syntaxhighlight lang="prolog">
egcd(_, 0, 1, 0) :- !.
egcd(A, B, X, Y) :-
Line 1,754 ⟶ 2,744:
A*X + B*Y =:= 1,
N is X mod B.
</syntaxhighlight>
{{Out}}
<pre>
Line 1,766 ⟶ 2,756:
=={{header|PureBasic}}==
Using brute force.
<
Declare main()
Declare.i mi(a.i, b.i)
Line 1,802 ⟶ 2,792:
If x > y - 1 : x = -1 : EndIf
ProcedureReturn x
EndProcedure</
{{out}}
<pre> MODULAR-INVERSE( 42, 2017) = 1969
Line 1,811 ⟶ 2,801:
=={{header|Python}}==
===Builtin function===
Since python3.8, builtin function "pow" can be used directly to compute modular inverses by specifying an exponent of -1:
<syntaxhighlight lang="python">>>> pow(42, -1, 2017)
1969
</syntaxhighlight>
===Iteration and error-handling===
Implementation of this [http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Iterative_method_2 pseudocode] with [https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm#Modular_inverse this].
<
lastremainder, remainder = abs(aa), abs(bb)
x, lastx, y, lasty = 0, 1, 1, 0
Line 1,831 ⟶ 2,827:
>>> modinv(42, 2017)
1969
>>> </
===Recursion and an option type===
Or, using functional composition as an alternative to iterative mutation, and wrapping the resulting value in an option type, to allow for the expression of computations which establish the '''absence''' of a modular inverse:
<
from itertools import (chain)
Line 1,926 ⟶ 2,922:
# MAIN ---
main()</
{{Out}}
<pre>
Line 1,935 ⟶ 2,931:
{{trans|Forth}}
<
[ tuck 1 0
[ swap temp put
Line 1,951 ⟶ 2,947:
nip ] is modinv ( n n --> n )
42 2017 modinv echo</
{{out}}
<pre>1969</pre>
===Using Extended Euclidean Algorithm===
Handles negative args. Returns -1 for non-coprime args.
<syntaxhighlight lang="quackery"> [ dup 0 = iff
[ 2drop 1 0 ]
done
dup unrot /mod
dip swap recurse
tuck 2swap *
dip swap - ] is egcd ( n n --> n n )
[ dup 0 < if negate
over 0 < if
[ swap negate
over tuck mod
- swap ]
dup rot 2dup egcd
2swap 2over rot *
unrot * + 1 != iff
[ drop 2drop -1 ]
done
nip swap mod ] is modinv ( n n --> n )
say " 42 2017 modinv --> " 42 2017 modinv echo cr ( --> 1969 )
say " 40 1 modinv --> " 40 1 modinv echo cr ( --> 0 )
say " 52 -217 modinv --> " 52 -217 modinv echo cr ( --> 96 )
say "-486 217 modinv --> " -486 217 modinv echo cr ( --> 121 )
say " 40 2018 modinv --> " 40 2018 modinv echo cr ( --> -1 )</syntaxhighlight>
{{out}}
<pre> 42 2017 modinv --> 1969
40 1 modinv --> 0
52 -217 modinv --> 96
-486 217 modinv --> 121
40 2018 modinv --> -1
</pre>
=={{header|Racket}}==
<
(require math)
(modular-inverse 42 2017)
</syntaxhighlight>
{{out}}
<
1969
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
my ($c, $d, $uc, $vc, $ud, $vd) = ($n % $modulo, $modulo, 1, 0, 0, 1);
my $q;
Line 1,979 ⟶ 3,014:
}
say inverse 42, :modulo(2017)</
=={{header|REXX}}==
<
parse arg x y . /*obtain two integers from the C.L. */
if x=='' | x=="," then x= 42 /*Not specified? Then use the default.*/
Line 1,998 ⟶ 3,033:
if $<0 then $= $ + ob /*Negative? Then add the original B. */
return $</
{{out|output|text= when using the default inputs of: <tt> 42 2017 </tt>}}
<pre>
Line 2,005 ⟶ 3,040:
=={{header|Ring}}==
<
see "42 %! 2017 = " + multInv(42, 2017) + nl
Line 2,024 ⟶ 3,059:
if multInv < 0 multInv = multInv + b0 ok
return multInv
</syntaxhighlight>
Output:
<pre>
42 %! 2017 = 1969
</pre>
=={{header|RPL}}==
Using complex numbers allows to ‘parallelize’ calculations and keeps the stack depth low: never more than 4 levels despite the simultaneous use of 6 variables: r, r’, u, u’, q - and b for the final touch.
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
DUP ROT 1 R→C ROT 0 R→C
'''WHILE''' DUP RE '''REPEAT'''
OVER RE OVER RE / FLOOR
OVER * NEG ROT +
'''END'''
DROP C→R ROT MOD
SWAP 1 == SWAP 0 IFTE
≫ ‘'''MODINV'''’ STO
|
'''MODINV''' ''( a b -- x )'' with ax = 1 mod b
3: b 2: (r,u)←(a,1) 1:(r',u')←(b,0)
While r' ≠ 0
q ← r // r'
(r - q*r', u - q*u')
Forget (r',u') and calculate u mod b
Test r and return zero if a and b are not co-prime
|}
{{in}}
<pre>
123 456 MODINV
42 2017 MODINV
</pre>
{{out}}
<pre>
2: 1969
1: 0
</pre>
=={{header|Ruby}}==
<
def extended_gcd(a, b)
last_remainder, remainder = a.abs, b.abs
Line 2,050 ⟶ 3,124:
end
x % et
end</
<pre>
> invmod(42,2017)
Line 2,056 ⟶ 3,130:
Simplified equivalent implementation
<
def modinv(a, m) # compute a^-1 mod m if possible
raise "NO INVERSE - #{a} and #{m} not coprime" unless a.gcd(m) == 1
Line 2,069 ⟶ 3,143:
inv
end
</syntaxhighlight>
<pre>
> modinv(42,2017)
=> 1969
</pre>
The OpenSSL module has modular inverse built in:
<syntaxhighlight lang="ruby">require 'openssl'
p OpenSSL::BN.new(42).mod_inverse(2017).to_i</syntaxhighlight>
=={{header|Run BASIC}}==
<
end
Line 2,094 ⟶ 3,171:
if multInv < 0 then multInv = multInv + b0
[endFun]
end function</
{{out}}
Line 2,102 ⟶ 3,179:
=={{header|Rust}}==
<
let mut mn = (module, a);
let mut xy = (0, 1);
Line 2,119 ⟶ 3,196:
fn main() {
println!("{}", mod_inv(42, 2017))
}</
{{out}}
Line 2,127 ⟶ 3,204:
Alternative implementation
<
fn modinv(a0: isize, m0: isize) -> isize {
if m0 == 1 { return 1 }
Line 2,146 ⟶ 3,223:
fn main() {
println!("{}", modinv(42, 2017))
}</
{{out}}
Line 2,155 ⟶ 3,232:
=={{header|Scala}}==
Based on the ''Handbook of Applied Cryptography'', Chapter 2. See http://cacr.uwaterloo.ca/hac/ .
<
def gcdExt(u: Int, v: Int): (Int, Int, Int) = {
@tailrec
Line 2,170 ⟶ 3,247:
val (i, j, g) = gcdExt(a, m)
if (g == 1) Option(if (i < 0) i + m else i) else Option.empty
}</
Translated from C++ (on this page)
<
def modInv(a: Int, m: Int, x:Int = 1, y:Int = 0) : Int = if (m == 0) x else modInv(m, a%m, y, x - y*(a/m))
</syntaxhighlight>
{{out}}
Line 2,192 ⟶ 3,269:
If a and b are not coprime (gcd(a, b) <> 1) the exception RANGE_ERROR is raised.
<
in var bigInteger: b) is func
result
Line 2,234 ⟶ 3,311:
raise RANGE_ERROR;
end if;
end func;</
Original source: [http://seed7.sourceforge.net/algorith/math.htm#modInverse]
Line 2,240 ⟶ 3,317:
=={{header|Sidef}}==
Built-in:
<syntaxhighlight lang
Algorithm implementation:
<
var (t, nt, r, nr) = (0, 1, n, a % n)
while (nr != 0) {
Line 2,255 ⟶ 3,332:
}
say invmod(42, 2017)</
{{out}}
<pre>
Line 2,263 ⟶ 3,340:
=={{header|Swift}}==
<
@inlinable
public func modInv(_ mod: Self) -> Self {
Line 2,282 ⟶ 3,359:
}
print(42.modInv(2017))</
{{out}}
Line 2,290 ⟶ 3,367:
=={{header|Tcl}}==
{{trans|Haskell}}
<
if {$b == 0} {
return [list 1 0 $a]
Line 2,306 ⟶ 3,383:
while {$i < 0} {incr i $m}
return $i
}</
Demonstrating
<
catch {
puts "2 %! 4 = [modInv 2 4]"
} msg; puts $msg</
{{out}}
<pre>
Line 2,320 ⟶ 3,397:
=={{header|Tiny BASIC}}==
2017 causes integer overflow, so I'll do the inverse of 42 modulo 331 instead.
<
PRINT "Modular inverse."
PRINT "What is the modulus?"
Line 2,338 ⟶ 3,415:
LET B = B - M
GOTO 30
</syntaxhighlight>
{{out}}
<pre>Modular inverse.
Line 2,350 ⟶ 3,427:
Another version:
{{trans|GW-BASIC}}
<
REM Modular inverse
LET E=42
Line 2,378 ⟶ 3,455:
130 LET M=D
RETURN
</syntaxhighlight>
{{out}}
<pre>
Line 2,385 ⟶ 3,462:
=={{header|tsql}}==
<
AS (
SELECT
Line 2,418 ⟶ 3,495:
)
SELECT *
FROM ModularInverse</
== {{header|TypeScript}} ==
{{trans|Pascal}}
<syntaxhighlight lang="javascript">
// Modular inverse
function modInv(e: number, t: number): number {
var d = 0;
if (e < t) {
var count = 1;
var bal = e;
do {
var step = Math.floor((t - bal) / e) + 1;
bal += step * e;
count += step;
bal -= t;
} while (bal != 1);
d = count;
}
return d;
}
console.log(`${modInv(42, 2017)}`); // 1969
</syntaxhighlight>
{{out}}
<pre>
1969
</pre>
=={{header|uBasic/4tH}}==
{{trans|C}}
<syntaxhighlight lang="text">Print FUNC(_MulInv(42, 2017))
End
Line 2,446 ⟶ 3,551:
If g@ < 0 Then g@ = g@ + c@
Return (g@)</
{{trans|Perl}}
<syntaxhighlight lang="text">Print FUNC(_mul_inv(42, 2017))
Print FUNC(_mul_inv(40, 1))
Print FUNC(_mul_inv(52, -217))
Line 2,471 ⟶ 3,576:
If (e@ > 1) Return (-1) ' No inverse'
If (c@ < 0) c@ = c@ + b@
Return (c@)</
{{out}}
<pre>1969
Line 2,485 ⟶ 3,590:
{{works with|Korn Shell}}
{{works with|Zsh}}
{{trans|PowerShell}}<
typeset -i a=$1 n=$2
if (( n < 0 )); then (( n = -n )); fi
Line 2,508 ⟶ 3,613:
}
invmod 42 2017</
{{Out}}
Line 2,514 ⟶ 3,619:
=={{header|VBA}}==
{{trans|Phix}}<
Private Function mul_inv(a As Long, n As Long) As Variant
If n < 0 Then n = -n
Line 2,545 ⟶ 3,650:
Debug.Print mul_inv(-486, 217)
Debug.Print mul_inv(40, 2018)
End Sub</
<pre> 1969
0
Line 2,551 ⟶ 3,656:
121
a is not invertible</pre>
=={{header|V (Vlang)}}==
<syntaxhighlight lang="Zig">
fn main() {
println("42 %! 2017 = ${mult_inv(42, 2017)}")
}
fn mult_inv(aa int, bb int) int {
mut a, mut b := aa, bb
mut x0, mut t := 0, 0
mut b0 := b
mut x1 := 1
if b == 1 {return 1}
for a > 1 {
q := a / b
t = b
b = a % b
a = t
t = x0
x0 = x1 - q * x0
x1 = t
}
if x1 < 0 {x1 += b0}
return x1
}
</syntaxhighlight>
{{out}}
<pre>
42 %! 2017 = 1969
</pre>
=={{header|Wren}}==
{{libheader|Wren-big}}
<
var a = BigInt.new(42)
var b = BigInt.new(2017)
System.print(a.modInv(b))</
{{out}}
Line 2,566 ⟶ 3,702:
=={{header|XPL0}}==
<
int X;
def A=42, M=2017;
Line 2,572 ⟶ 3,708:
if rem(A*X/M) = 1 then [IntOut(0, X); exit];
Text(0, "Does not exist");
]</
{{out}}
<pre>
Line 2,580 ⟶ 3,716:
=={{header|zkl}}==
{{trans|Haskell}}
<
if(b==0) return(1,0,a);
q,r:=a.divr(b); s,t,g:=gcdExt(b,r); return(t,s-q*t,g);
}
fcn modInv(a,m){i,_,g:=gcdExt(a,m); if(g==1) {if(i<0)i+m} else Void}</
divr(a,b) is [integer] (a/b,remainder)
{{out}}
| |||