Frage zu negativen und positiven Exponenten in rekursiver Methode

[chillipalmer]

Nabend!

Hab hier ne Aufgabe, bei der negative und positive Exponenten aus ganzen Zahlen mit einer Basis aus reellen Zahlen berechnet werden sollen. Hab soweit alles hinbekommen, wollte aber mal wissen, ob es da ne bessere Lösung gibt, außer irgendwelche vordefinierten Methoden aus der Math Class zu benutzen? Muss aber rekursiv sein.

[HIGHLIGHT="Java"]
class Aufgabe_6_7_NegativeExponenten {
public static void main(String[] args) {

double b = 2.0;
int e = -3;
System.out.println(b + " hoch " + e + " ist: " + hoch(b,e));

}

static double hoch( double b , int e )
{
if( e == 0 ) return 1.0;
if( e == 1 ) return b;
if(e == -1) return 1 / b;
if(e < -1) return (1 / (hoch(b, (e * -1)) ));
return( b * hoch( b , e-1 ) );
}
}[/HIGHLIGHT]

 

[0x7F800000]

Teil1: (versehentlich wegeditiert)
Nunja, das ist jetzt so eine "theoretisch hübsche" Lösung um rekursion zu demonstrieren, hoffe ich doch?

Normalerweise geht das wesentlich schneller.
Idee:
zB. bei 7^21 rechnet man
7^21=(7^16)*(7^4)*7
Das sind dann insgesammt 5 multiplikationen, statt wie bei deiner methode
7^21=7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7
(20 Multiplikationen)
Das ist bereits bei solch mikrigen Exponenten erheblich, wenn die Exponenten ein paar Hundert stellen haben, ist das mit deiner O(exponent) methode nicht in vertretbarer Zeit auszuwerten, in O(log(exponent)) geht das dagegen locker.

=> Da deine Lösung also lediglich schön sein soll, statt zu funktionieren, würde ich die zeilen 13 und 14 einfach rauslöschen, weil sie unnötig sind.
________________________________________________
Teil 2:

Ooooh, manoman, deine Lösung ist unter Java echt nur rein theoretisch funktionsfähig:
mein Java compiler (der standart java-compiler) optimiert die Endrekursion gar nicht weg, deine Methode müllt deshalb den speicher voll und schmeißt exceptions, selbst bei gaaanz mikrigen exponenten, hier ein beispiel:
[HIGHLIGHT="Java"]
public class _ {

public static double powPositive(double b, int e){
if(e==0) return 1;
double temp=powPositive(b,e/2);
temp*=temp;
if((e&1)==1)temp*=b;
return temp;
}

public static double pow(double d, int e){
if(e<0){
return 1/powPositive(d,-e);
}else{
return powPositive(d,e);
}
}


static double hoch( double b , int e ){
if( e == 0 ) return 1.0;
if( e == 1 ) return b;
if(e == -1) return 1 / b;
if(e < -1) return (1 / (hoch(b, (e * -1)) ));
return( b * hoch( b , e-1 ) );
}

public static void main(String[] args) {
double b=1.0000001;
int e=10000000;
System.out.println(
pow(b,e)+"\n"
+Math.pow(b,e)+"\n"
//+hoch(b,e) //<---- geht gar nicht, stackOverflow...
);
}
}
[/HIGHLIGHT]
hab da vorne alles mit meiner (merkwürdig implementierten ebenfalls rekursiven) variante verglichen. Stimmt auf paar nachkommastellen mit "referenzwert" übererein, und verreckt wenigstens nicht bei 5-stelligen Exponenten

 

[Der Müde Joe]

so auf die schnelle:

     public static double pow(double d , int exp) {
    	 return (exp > 0) ? pow1(d, exp) : 1 / pow1(d, -exp); 
     }
     
     private static double pow1(double d, int exp) {
    	 if (exp == 0) {
    		 return 1;
    	 }
    	 if(exp == 1) {
    		 return d;
    	 }
    	 if(exp%2 == 0) {
    		 return pow1(d, exp/2) * pow1(d, exp/2);
    	 } else {
    		 return d * pow1(d, exp-1);
    	 }
     }

 

[SlaterB]

> 7^21=(7^16)*(7^4)*7
> Das sind dann insgesammt 5 multiplikationen

kannst du das näher erläutern? ich komme auf 6

 

[Marco13]

EDIT: Mich hat's da jetzt auch erst rausgehauen... 7^4 * 7^4 ist NICHT 7^16
a = 7*7 => 1 mul
b = 7^4 = a*a => 1 mul
c = 7^8 = b*b => 1 mul
d = 7^16 = c*c => 1 mul
d*b*7 => 2 mul

 

[0x7F800000]

> 7^21=(7^16)*(7^4)*7
> Das sind dann insgesammt 5 multiplikationen

kannst du das näher erläutern? ich komme auf 6

Omfg, jetzt habe ich mich um +-1 verzählt, zerfetzt mich doch in kleine Stücke^^ :autsch:

edit: ne, zerfetzt lieber Den Müden Joe^^, schaut mal was er hier macht statt zu quadrieren:

return pow1(d, exp/2) * pow1(d, exp/2);

 

[SlaterB]

abgesehen von dem nicht wiederverwendeten Zwischenwert scheint es aber zumindest in diesem Beispiel auch auf 6 Mulitplikationen hinauszulaufen:
1. 7^2
2. 7^4
3. 7^5
4. 7^10
5. 7^20
6. 7^21

 

[0x7F800000]

Naja, die rekursive variante die ich angeschrieben hab benimmt sich zwar ein wenig anders, aber es läuft doch auch in O(lg(e))...

 

[SlaterB]

will doch niemand schlecht machen,
und wie ich gerade sehe macht sie doch genau das gleiche bis auf den Cache des Zwischenwerts (und Tricksereien wie das eingesparte %2)?

> double temp=powPositive(b,e/2);
hier wird bei e=21 auch b^10 gerechnet, gar nicht b^16

(und das soll wieder kein Vorwurf sein )

 

[0x7F800000]

hier wird bei e=21 auch b^10 gerechnet, gar nicht b^16

soll es ja auch nicht.
Die erste methode die ich skizziert habe, läuft in O(lg(e)) ist aber nicht rekursiv. Würde etwa so aussehen:
[HIGHLIGHT="Java"]
public static long pow(long base, long exponent){
long result=1;
for(long x=base; exponent>0;x*=x,exponent>>=1){
if((exponent&1)==1) result*=x;
}
return result;
}
[/HIGHLIGHT]
Das rechnet so wie in meinem ersten Beispiel.

Die rekursive variante läuft auch in O(lg(n)) aber multipliziert die Sachen in einer etwas anderen reihenfolge aus.

und wie ich gerade sehe macht sie doch genau das gleiche bis auf den Cache des Zwischenwerts (und Tricksereien wie das eingesparte %2)?

Tricksereien wie %2 sind wohl echt total egal.
Aber dass der Wert nicht gecachet wird macht doch grade den Unterschied zwischen O(n) und O(lg(n)) aus, also zwischen 1024 und 10, 1048576 und 20, einer million milliarden und 50 usw... Das tut schon weh.

 

[SlaterB]

> Aber dass der Wert nicht gecachet wird macht doch grade den Unterschied

klar, ich meinte, das ist kein interessanter Bestandteil des Algorithmus sondern ein allgemeines Prinzip,
das zu vergessen ist ein Flüchtigkeitsfehler, keine Strategieentscheidung oder so

 

[0x7F800000]

das zu vergessen ist ein Flüchtigkeitsfehler, keine Strategieentscheidung oder so

Sowieso. Das mit "5 Multiplikationen" war doch auch einer^^