ganzzahlige Potenz schnell berechnen

[Guest]

Habe eine Gleitkommazahl als Basis und eine ganzzahlige positive Zahl als Exponent

Math.pow(base,exp) verwended StrictMath und das ist grottig langsam.

double result = 1;
for (int i = 0; i < exp; i++){
    result *= base;
}

ist schon sehr viel besser, bei kleinen Exponenten schön schnell aber mein Exponent kann aber bis zu 1000 groß werden und das ist dann schon wieder sehr langsam.

Muss mehrere Milliarden solcher Berechnungen durchführen mit verschiedenen Basen und Exponenten und will nicht jedes mal Tage auf das Ergebnis warten.

Das muss man doch wesentlich beschleunigen können, z.B. die Zahl halbieren und nur die erste Hälfte "zusammenmultiplizieren" und dann das quadrat davon und man hat das Ergebnis. das ganze dann noch rekursiv, also Divide&Conqer und ratz fatz hat man das Ergebnis.
Bevor ich aber sowas selbst programmiere: gibts da noch eine bessere Lösung und gibts sowas vielleicht schon fertig als Algorithmus?

 

[0x7F800000]

bevor du sowas programmierst, solltest du dir im klaren sein, dass 2^1000 eh niemals in ein integer oder ein long reinpasst, erst recht keine Zahlen größer als 2.

Da müsstest du schon BigInteger nehmen. Wenn dort die Potenzierung nicht implementiert ist, dann mach's mit square & multiply, das was du gemeint hast verstehe ich nicht so recht.

 

[Guest]

Die Zahlen liegen dicht an 1, z.B. 1.01 oder 0.99 und das Ergebnis kommt in ein double, desshalb gibts keine Probleme mit der Größe der Zahl.

 

[0x7F800000]

achsoo, sowas wie "double^int" willst du also, ohne die blöden logarithmen ausrechnen zu müssen? Ja, das ist verständlich, :toll: .

Mit großen Ganzen zahlen würde das etwa so gehen:

     public static BigInteger pow(BigInteger base, BigInteger exp){
		BigInteger result=BigInteger.ONE;
		for(int i=0; i<exp.bitCount(); i++){
			if(exp.testBit(i)) result=result.multiply(base);
			base=base.multiply(base);
		}
		return result;
	}

mit double^int geht das völlig analog:

	public static double pow(double base, int exp){
		double result=1;
		while(exp>0){
			if( (exp&1)==1 ) result*=base;
			base*=base;
			exp>>=1;
		}
		return result;
	}

weiß jetzt nicht ob das wirklich schneller ist? ???:L

edit: hehe, ~16 mal schneller, goil^^

 

[Landei]

http://de.wikipedia.org/wiki/Schnelles_Potenzieren

http://www.programmers-corner.de/Articles/view/49/schnelles-Potenzieren-mit-Square-Multiply