Arytmetyka modularna (Java)
Jak przygotować operator mod dla typów prymitywnych – wyjaśniłam tutaj.
Teraz przygotujemy metody pozwalające wykonywać działania modularne.
Dodawanie modularne
public static long modAdd(long a, long b, long modulus) {
return mod(Math.addExact(a, b), modulus);
}
Odejmowanie modularne
public static long modSub(long a, long b, long modulus) {
return mod(Math.subtractExact(a, b), modulus);
}
Mnożenie modularne
public static long modMult(long a, long b, long modulus) {
return mod(Math.multiplyExact(a, b), modulus);
}
Potęgowanie modularne
public static long powExact(long a, long exp) {
if (exp < 0) {
throw new ArithmeticException("Wykładnik mniejszy od 0");
}
long w = 1L;
while (exp > 0) {
if ((exp & 1) == 1) {
w = Math.multiplyExact(w, Math.multiplyExact(w, a));
} else {
w = Math.multiplyExact(w, w);
}
exp >>= 1;
}
return w;
}
public static long modPow(long a, long exp, long modulus) {
return mod(powExact(a, exp), modulus);
}
Testy
Dodajemy 10 mod 24 + 4 mod 24.
Wynik: 14 mod 24
Odejmujemy 14 mod 24 – 16 mod 24.
Wynik: 22 mod 24
Mnożymy 10 mod 24 × 3 mod 24.
Otrzymujemy 6 mod 24.
Potęgujemy (10 mod 24)3 mod 24.
Wynik: 16 mod 24
Po uruchomieniu klasy ModMain:
long r1 = ModUtil.modAdd(10, 4, 24);
System.out.println(r1);
long r2 = ModUtil.modSub(14,16, 24);
System.out.println(r2);
long r3 = ModUtil.modMult(10, 3, 24);
System.out.println(r3);
long r4 = ModUtil.modPow(10, 3, 24);
System.out.println(r4);
na konsoli zobaczymy:
14 22 6 16
Klasa CongruenceTestMod2
long m = 24L;
long hour = 5;
System.out.println("Jest godzina: 5 mod 24 = " + ModUtil.mod(5, 24) + " mod 24");
System.out.println("Dodajemy 14 godzin:");
System.out.println("Jest godzina: modAdd(5, 14, 24) = " + ModUtil.modAdd(5, 14, 24) + " mod 24");
System.out.println("Mnożymy zegar przez 3 mod 24");
System.out.println("Jest godzina modMult(3, 19, 24) = " + ModUtil.modMult(3,19,24)+ " mod 24");
//-
long num = -125;
long pow = 3;
System.out.println(ModUtil.powExact(num, pow));
System.out.println((long)Math.pow(num,pow));
//-
System.out.println("Podnosimy zegar do potęgi modPow(9, 4, 24)");
System.out.println("Jest godzina modPow(9, 4, 24) = "+ModUtil.modPow(9,4,24));
Po uruchomieniu – na konsoli otrzymujemy:
Jest godzina: 5 mod 24 = 5 mod 24 Dodajemy 14 godzin: Jest godzina: modAdd(5, 14, 24) = 19 mod 24 Mnożymy zegar przez 3 mod 24 Jest godzina modMult(3, 19, 24) = 9 mod 24 -1953125 -1953125 Podnosimy zegar do potęgi modPow(9, 4, 24) Jest godzina modPow(9, 4, 24) = 9