Modular inverse: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
| (24 intermediate revisions by 11 users not shown) | |||
Line 581:
{{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}}
Line 607 ⟶ 633:
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 1,100 ⟶ 1,152:
return</syntaxhighlight>
{{out| Output}}<pre>1969</pre>
=={{header|Crystal}}==
Line 1,219 ⟶ 1,272:
-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}}==
Line 1,714 ⟶ 1,793:
{{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}}==
Line 1,783 ⟶ 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).
<syntaxhighlight lang="julia">function modinv
b0 = b
x0, x1 = zero(T), one(T)
Line 1,858 ⟶ 1,966:
</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}}==
Line 1,916 ⟶ 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}}==
Line 2,131 ⟶ 2,336:
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}}==
Line 2,202 ⟶ 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}}==
Line 2,481 ⟶ 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===
Line 2,626 ⟶ 2,952:
<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}}==
Line 3,291 ⟶ 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}}
<syntaxhighlight lang="
var a = BigInt.new(42)
| |||