Schnelles Potenzieren

Hallo Liebes Forum,

Ich habe folgende Aufgabe:
Die Berechnung der Potenzfunktion x^n kann für ganze Zahlen n≥0 durch eine Reduktion des Exponenten in folgender Form erfolgen:

x^n = {
1 für n = 0
(x*x)^n/2 für n grade und n > 1
x * x ^ n-1 sonst


1. Prüfen Sie an dem Zahlenbeispiel x = 2 und n = 13, ob die Berechnung der Potenz mit diesem Algorithmus korrekt ist.

2. Schreiben Sie eine rekursive Methode zur Berechnung der Potenz und ermitteln Sie die Anzahl der rekursiven Aufrufe in Abhängigkeit von der Größe des Exponenten n.
Zu erstens habe ich folgende Gedanken:

erster Durchlauf: 2 * (2 ^ 13 - 1) = 8192
zweiter Durchlauf: ((2 * 2)^ 12 / 2) = 4096
dritter Durchlauf: ((2 * 2) ^ 6 / 2) = 64
vierter Durchlauf: 2 * (2 ^ 3 - 1) = 8
fünfter Durlauf: ((2 * 2) ^ 2 / 2) = 4
sechster Durchlauf: 2 * (2 ^ 1 - 1) = 2
siebenter Durchlauf : n = 0 return 1;
Zu 2. habe folgenden Code:


Java:
public static double fastPotRek(double x, int n){
        // TODO: recursive variation
        if (n == 0) return 1;
        else if (n % 2 == 0 && n > 1) return fastPotRek(x*x,n/2);
        else return fastPotRek(x*x,n-1);
    }
Die Aufrufe lasse ich mit einer public static int innerhalb der Klasse zählen, da kommt Momentan auch 7 raus wie in meiner Aufzählung also läuft das immerhin :D

Jetzt ist meine Frage wo ist mein Denkfehler?
 
Und.... du kannst dir noch zunutzemachen:
2^x=1<<x;
 
Du hast noch Math.pow(...,n/2); o. Ä. vergessen. ;)
Naja ich vermute mal es geht darum es nicht mit Math.pow zu lösen, sonst wäre die Aufgabe ja hinfällig, ich könnte genauso gut dann auch einfach Math.pow(x,n) angeben und wäre fertig.

Der Bitshift basiert doch auch darauf Math.pow zu ersetzen, aber das ist ja alles nicht sinn der Sache.
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben