Schnelles Potenzieren

[BlueLizard]

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:

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

Jetzt ist meine Frage wo ist mein Denkfehler?

 

[abc66]

Du hast noch Math.pow(...,n/2); o. Ä. vergessen.

 

[abc66]

Und.... du kannst dir noch zunutzemachen:
2^x=1<<x;

Java Bitshift to Replace Math.pow

I need to replace a Math.pow in Java with bitshift. for (int i = n - 1; i >= 0; i--) Math.pow(16, n - i - 1) Where n is the length of a hex number. 13304fb would mean n= 7. It's basically

stackoverflow.com

 

[BlueLizard]

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.

 

[Hutzli]

Hallo

Ich sag dir mal, wo der Fehler liegt:

x * x ^ n-1 sonst

Vergleiche das mit deiner letzten Bedingung (Beachte die Klammersetzung):

else return fastPotRek(x*x,n-1);

 

[BlueLizard]

Hallo

Ich sag dir mal, wo der Fehler liegt:

Vergleiche das mit deiner letzten Bedingung (Beachte die Klammersetzung):

Danke ist jetzt klar woraus du hinaus wolltest, der Wald vor lauter Bäumen