Modular inverse: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(Modular inverse in Chipmunk Basic, QBasic and True BASIC) |
m (→{{header|Wren}}: Minor tidy) |
||
| (11 intermediate revisions by 8 users not shown) | |||
Line 1,152:
return</syntaxhighlight>
{{out| Output}}<pre>1969</pre>
=={{header|Crystal}}==
Line 1,271 ⟶ 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,766 ⟶ 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,835 ⟶ 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 2,008 ⟶ 2,064:
<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}}==
Line 2,735 ⟶ 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,880 ⟶ 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,545 ⟶ 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)
| |||