Logarithmus Algorithmus

[j_new]

Hallo,

ich bin JAVA Anfänger und stehe vor folgendem Problem. Ich möchte n^2 * log(n) berechnen.
Jedoch ohne Hilfe von irgendeiner Math Bibliothek. Das heißt ich möchte mir den Algorithmus selbst überlegen.

n^2 habe ich so gelöst

int n = 5;
int k = 0;
		
//n*n
for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		k = k + 1;
	}
}
System.out.println(k);

k ist hier mein Ergebnis

für log habe ich jetzt schon folgenden Denkanstoß bekommen: Intervallhalbierung
Code: (Breitenbeschränkung entfernen)

while (k > 0)
{
  k = k / 2; // integer-division!
}

Das kommt mir nu ein bisschen komisch vor, und ich weiß nicht wo hier dann mein Ergebnis stehen soll.
Kann mir da von euch vielleicht jemand weiterhelfen? Oder hat irgendjemand eine andere Idee wie man dieses Problem lösen kann? Ich habe bei google keinerlei passende Lösung gefunden.


Danke und liebe Grüße

 

[Logaff]

Ok wenn du wirklich nen eignen algo machen willst, Logarithmus ist die Umkehrung der Potzenierung

oder du gucken hier
HIER!

 

[Landei]

Es gibt mehrere Potenzreihen, um den Logarithmus (meist den natürlichen) zu berechnen, z.B. Logarithmus ? Wikipedia

 

[j_new]

Wenn ich so vorgehe, dann habe ich erst recht wieder das Problem, dass bei mir steht:

n = 2^x

ich will mir aber das x ausrechnen. Jetzt stehe ich wieder vor dem Problem, dass ich laut meinem mathematische Verständinss einen Log brauche, und genau diesen möchte ich ausprogrammieren, da ich erst dann von mir behaupten kann, dass ich den Algorithmus verstanden habe.

 

[Logaff]

guck noch mal hier
Logarithmus ? Wikipedia

ich finde dies mit den wurzeln lässt sich gut machen, und jeder logarithmus kann als logarithmus zur basis e, ln dagestellet werden

 

[Final_Striker]

Schau dir die beiden Formeln an: Wie berechnet der Taschenrechner den Logarithmus? | jomo.org

 

[Landei]

Wenn ich so vorgehe, dann habe ich erst recht wieder das Problem, dass bei mir steht:

n = 2^x

ich will mir aber das x ausrechnen. Jetzt stehe ich wieder vor dem Problem, dass ich laut meinem mathematische Verständinss einen Log brauche, und genau diesen möchte ich ausprogrammieren, da ich erst dann von mir behaupten kann, dass ich den Algorithmus verstanden habe.

Häh? n = 2^x, also x = ln(n)/ln(2), und die verlinkte Formel kann den Logarithmus ausrechnen. Wo ist das Problem?

[Edit] Ach so, du bezogest dich anscheinend auf den Vorredner...

 

[Crian]

Mache dir vorher klar, welche Operationen du verwenden willst (darfst), und welche nicht. Statt

int n = 5;
int k = 0;
		
for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		k = k + 1;
	}
}
System.out.println(k);

täte es vielleicht ja auch

int n = 5;
int k = n * n;
System.out.println(k);

Eine mathematische Bibliothek wurde dafür nun auch nicht benutzt.

 

[Landei]

Hier der natürliche Logarithmus ohne Bibliothek:

public class Logarithm {
    
    private static double sqrtE = 1.6487212707001281468486507878141635716537761007101480115750;
    
    private static double ln_x_smaller_2(double x) {
        double x_1 = x - 1;
        double power = 1.0;
        double result = 0;
        double delta = 1;
        double factor = 1;
        for(int i = 1; delta > 0.000000001; i++) {
            power *= x_1;
            delta = power / i;
            result += delta * factor;
            factor = -factor;
        }
        return result;    
    }
    
    
    public static double ln(double x) {
        assert (x > 0);
        int count = 0;
        while(x > 1.9) {
            x = x / sqrtE;
            count ++;
        }    
        return  0.5*count + ln_x_smaller_2(x);
    }
}

Die Genauigkeit lässt sich über delta steuern.

Dann gilt:
log2(x) = ln(x) / ln(2) = ln(x) / 0.69314718

 

[Andi_CH]

noch die Version mit der Reihenentwicklung.

public class Logarithmus {

	private final static double epsilon = 1E-6;

	public static double abs (double value) {
		if (value <0)
			return value * -1.0;
		else
			return value;
	}

	public static double pow (double value, int exp) {
		if (exp == 1)
			return value;
		else
			return value * pow(value, exp - 1);
	}

	public static double ln(double value) {
		double k = ((value - 1.0) / (value + 1));
		double temp = 0.0;
		double lastResult = 0.0;
		int i = 1;
		do {
			lastResult = 2.0 * temp;
			temp += (1.0 / i) * pow(k, i);
			// System.out.println("Value : " + value + ", Zw.resultat : " + (2 * temp) + ", delta : " + abs(lastResult - 2.0*temp));
			i += 2;
		} while ((abs(lastResult - 2.0*temp) > epsilon) || (i>1E6));
		System.out.println("Anz loops : " + ((i-1)/2));
		return 2.0 * temp;
	}

	public static void main(String... args) {
		double lnres = ln(10);
		System.out.println(lnres);
		System.out.println(Math.pow(Math.E, lnres));
		System.out.println(Math.log(10));
		System.out.println(abs(Math.log(10)-lnres));
	}
}

 

[j_new]

Wow, danke!
So ein Logarithmus ist wesentlich komplexer als ich dachte. Wäre ich nie drauf gekommen, ...

lg

 

[Landei]

Statt die aktuelle Potenz von k jedesmal komplett neu zu berechnen, solltest du sie dir merken und einfach in der Schleife mit k² multiplizieren.

 

[Andi_CH]

Wow, danke!
So ein Logarithmus ist wesentlich komplexer als ich dachte. Wäre ich nie drauf gekommen, ...

lg

Ja, da lernt man Math.log direkt schätzen