schnelles Potenzieren mit Square & Multiply
28.02.2008
Author: N43
KommentareMit dem naiven Algorithmus zum Berechnen der Potenz würde man c-mal a mit sich selbst multiplizieren.
Dies kann man beschleunigen, wenn man die Tatsache, dass und
ist ausnutzt.
Damit ergibt sich folgende rekursive Berechnungsformel, die die Laufzeit hat, da c in jedem Schritt halbiert wird.
Mit dem Square & Multiply Algorithmus erreicht man also eine sehr gute Laufzeit im Vergleich zum naiven Algorithmus mit .
Der C-Code demonstriert nochmals diesen Algorithmus.
CPP - Code:
int pot(int a, int c)
{
int res;
if (c == 0) {
return 1;
}
res = pot (a, c/2); // a^n berechnen
res = res * res; // damit (a^n)^2 = a^2n bestimmen
// c war ungerade?
if (c % 2) {
// also noch mit a multiplizieren
res = res * a;
}
return res;
}
{
int res;
if (c == 0) {
return 1;
}
res = pot (a, c/2); // a^n berechnen
res = res * res; // damit (a^n)^2 = a^2n bestimmen
// c war ungerade?
if (c % 2) {
// also noch mit a multiplizieren
res = res * a;
}
return res;
}
SAG ich nicht
27.05.2009
Author: SAG ich nicht
Zu kompliziert
N43
30.05.2009
Author: N43
Wenn du mir sagst, was du daran zu kompliziert findest, dann könnte ich die Erklärung auch verbessern.
N43
P.S.: Anstatt "SAG ich nicht" darfst du auch gerne einen Nickname verwenden.
Unbekannt
11.05.2011
Author: Unbekannt
Super erklärt!