# Logarithmus Algorithmus



## j_new (11. Mai 2011)

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 (11. Mai 2011)

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

oder du gucken hier 
HIER!


----------



## Landei (11. Mai 2011)

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


----------



## j_new (11. Mai 2011)

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 (11. Mai 2011)

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 (11. Mai 2011)

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


----------



## Landei (11. Mai 2011)

j_new hat gesagt.:


> 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 (11. Mai 2011)

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 (11. Mai 2011)

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 (11. Mai 2011)

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 (11. Mai 2011)

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

lg


----------



## Landei (11. Mai 2011)

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 (11. Mai 2011)

j_new hat gesagt.:


> 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


----------

