In dieser Aufgabe sollen schnelle Methoden des Potenzierens untersucht werden.
Implementieren Sie dazu zunächst eine langsame Variante. Ihre Lösung muss rekursiv sein und darf keine Schleifen enthalten. Verwenden Sie dazu die Tatsache, dass man die Power-Funktion auch induktiv definieren kann:
- a0 mod n = 1 (Induktionsanfang)
- ae mod n = a * (ae-1mod n) (Induktionsschritt)
Zählen Sie die notwendigen rekursiven Aufrufe der Methode powerMod.
Implementieren Sie nun eine schnelle rekursive Variante. Nutzen Sie dazu die Beobachtung, dass man den Induktionsschritt auch ausdrücken kann als:
- (ae/2 mod n)2, wenn e gerade ist
- a * (a(e-1)/2 mod n)2, sonst
Hinweis: Berechnen Sie den Wert ae/2 nicht zweimal!
package de.hsrm.cs.ads;
/*
* Modular Power
* - compute a^e mod n
* - implement recursion vs iteration
*/
public class Power {
// Performance counter
public static int calls = 0;
public static int powerMod(int a, int e, int n) {}
public static int fastPowerMod(int a, int e, int n) {}
public static void testPower(int a, int e, int n, int result, boolean mode) {
int testResult;
// Check mode
if (mode) {
// Use slow mode
testResult = fastPowerMod(a, e, n);
} else {
// Use fast mode
testResult = powerMod(a, e, n);
}
// Simple debug message
System.out.format("Es wurde %d^%d mod %d = %d berechnet (richtig: %d)\n", a, e, n, testResult, result);
}
public static void main(String[] args) {
// Tests (slow mode)
calls = 0;
System.out.format("Slow-Mode tests\n");
testPower( 2, 8, 1000, 256, false);
System.out.format("Calls: %d\n\n", calls);
// Tests (fast mode)
calls = 0;
System.out.format("Fast-Mode tests\n");
testPower( 2, 16, 100, 36, true);
System.out.format("Calls: %d\n", calls);
}
}
Subato
