# Arkussinus effizient berechnen



## Ark (5. Aug 2009)

Der Titel sagt eigentlich alles.

Wie kann ich die Umkehrung des Sinus effizient berechnen? Ich muss nämlich arcsin nachbauen, aber die Taylorreihe konvergiert viel zu langsam. Hier mein Code in Java:

```
private static double iarcsin(double x){
		double res=x;
		double xx=x;
		x*=x;
		double coeff=1;
		int n=1;
		double delta;
		while(true){
			n++;
			coeff/=n;
			xx*=x;
			n++;
			delta=xx/n*coeff;
			// System.out.println("n="+n+"\tdelta="+delta+"\tres="+res);
			if(delta<=0.000000000000000001) return res;
			res+=delta;
			coeff*=n;
		}
	}
```
Gibt es da effizientere Algorithmen?

Ark


----------



## Marco13 (5. Aug 2009)

Nur um das zu klären: Ist das Ziel wirklich, das Ding _nachzubauen_, oder (ver)suchst du eine schnellere Implementierung als die von Math. ? Letzteres dürfte kaum möglich sein. Für ersteres könnte ich aber auch nur eine Websuche starten....


----------



## Rainer64 (5. Aug 2009)

Welche Genauigkeit brauchst du denn?



Ark hat gesagt.:


> ```
> if(delta<=0.000000000000000001) return res;
> ```
> Ark


Denke da an Spline-Interpolation ( da wird das Intervall [-1,1] in sehr viele kleine Polynome niedrigen Grades aufgeteilt). Der Nachteil ist, dass die Polynomkoeffizienten in einer Tabelle (Array) abgelegt werden müssen. Wenn man die Genauigkeit hochtreibt, steigt dann auch die Größe des Arrays. Muss man abwägen.

Stelle mir aber vor, dass bei unfähren Werten (wie arcsin(0.99999) )  das Berechnen über Splines bei einer Genauigkeit von z.B. 0.001 schneller ist.


----------



## 0x7F800000 (6. Aug 2009)

Also, ich versuch's mal in kürze und ohne detaillierte beweise zu skizzieren:

*1. Def:* Wir nennen eine summierbare, positive, streng monoton fallende Folge von reellen zahlen *gut* wenn jedes Folgenglied kleiner als die Summe der nachfolgenden Folgenglieder ist. Andernfalls nennen wir die Folge *schlecht*. "Summierbar" heißt einfach: die Summe ist endlich, auf gut mathematisch: Folge ist in l^1.
Diese Summe bezeichnen wir als Radius.

*2. Satz:* Für gute Folgen gilt: Man kann jede beliebige Zahl mit betrag kleiner gleich als Radius darstellen, indem man alle Folgenglieder mit einem Vorzeichen versieht und aufsummiert. Ich betone nochmal: ALLE. Man darf keine weglassen, man muss jedes Folgenglied entweder addieren oder subtrahieren.

Beweis: Man mache die fallunterscheidung, dass es
(a) gar keine Vorzeichenwechsel gibt. dann konvergiert's gegen +R oder -R
(b) endlich viele vorzeichenwechsel gibt. Dann ist die Approximation der Zahl nach endlich vielen schritten fertig, und die restlichen glieder summieren sich zu 0
(c) unendlich viele Vorzeichenwechsel gibt. Dann kann man zeigen, dass der fehler durch das Folgenglied beschränkt ist, an dem ein Vorzeichenwechsel stattfand. Da gute Folgen insbesondere Nullfolgen sind, wird auch der Fehler unendlich klein.

Wenn man den beweis ordentlich durchführt, dann bemerkt man, dass man das Vorzeichen immer so wählen muss, dass man in die richtung der zu approximierenden zahl läuft.

*3. Bemerkung* Man kann für schlechte folgen zeigen, dass sie manchmal bei der approximation so weit über das ziel hinausschießen, dass sie nicht mehr zurückkommen können. Bei guten Folgen passiert das nie.

*4. Satz*
Ist eine Funktion f:[0,+inf)->[0,+inf) mit f(0)=0 konkav, und ist die Folge (f(2^-k))_k summierbar, dann ist diese Folge auch gut.

Beweis: hinschreiben, an geometrische reihe denken.

*5. Korollar*
Die Folge (arctan(2^-k))_k ist gut.
Man kann in der Freizeit schätzen, dass R>1.74 ist, insbesondere können durch "vorzeichenwechselnde summen" dieser Folge alle zahlen zwischen [-pi/2, +pi/2] dargestellt werden.

*6. Algorithmus: CORDIC*
Alle winkeln zwischen [-pi/2, +pi/2] können durch summe der Winkeln arctan(2^-k) mit gemäß Satz 2 gewählten Vorzeichen dargestellt werden.
Hat man einen punkt (x,y) in der rechten halbebene gegeben, und will man den das Argument (winkel zwischen x-Achse und der Richtung zum Punkt) finden, dann dreht man den Punkt (x,y) mit rotationsmatrizen der Form

```
cos(a_k)   -sin(+-a_k)
sin(+-a_k)    cos(a_k)
```
solange hin und her, bis der punkt auf der x-achse landet, und addiert am ende die a_k's mit entsprechendem vorzeichen auf.
Damit es geht, muss die Folge der winkeln a_k gut sein.

Damit es schneller geht, klammert man den cosinus aus der rotationsmatrix aus, dann bleibt in der matrix nur noch:

```
1                 -tan(+-a_k)
tan(+-a_k)    1
```
stehen. Wenn y_k negativ ist, dreht man nach links, ansonsten nach rechts. Da der ausgeklammerte Kosinus für alle diese a_k's positiv ist, hat er auf das vorzeichen der y_k keine auswirkungen, und kann einfach weggeschmissen werden.

Damit es noch schneller geht, wählt man die Folge a_k als arctan(2^-k), dann steht in der matrix nur noch:

```
1            +-2^-k
+-2^-k        1
```
Wenn's drauf ankommt, kann man diese multiplikationen mit sehr billigen bitschifts realisiert werden.

Die dazugehörigen Winkeln arctan(2^-k) kann man schon im voraus alle berechnen, am ende braucht man sie nur noch mit einem entsprechenden Vorzeichen aufzuaddieren.

*7. Bemerkung *
Funktion, die zu x,y den Winkel rausfindet ist der gut bekannte atan2.
acos und asin usw. lassen sich darauf schnell mit dem Satz des Pythagoras zurückführen.

*8. Implementierung in java*

```
public class CORDIC {
	
	public static final int N=60;
	public static double[] angles;
	static{
		//einmalige initialisierung, kann solange dauern wie sie will, 
		//daher können lahme reihenentwicklungen verwendet werden
		angles=new double[N];
		double pow_2=1;
		
		for(int i=0; i<N; i++, pow_2/=2){
			angles[i]=series_atan(pow_2);
		}
		
		//bekannte werte im bereich wo es schlecht konvergiert per hand nachbessern
		angles[0]=Math.PI/4;
	}
	
	/*
	 * lahme implementierung von Arkustangens
	 * Die reihe erhält man, indem man die ableitung von arkustangens betrachtet
	 * diese ist 1/(1+x^2)
	 * die Taylorreihe von 1/(1+z) lässt sich leicht bestimmen
	 * darein setzt man z=x^2 ein
	 * auf [-1,1] konvergiert die reihe gleichmäßig, also darf man zum aufleiten das 
	 * Integral mit der summe vertauschen
	 * Am ende erhält man 
	 * 
	 * \atan(x)=\sum_{k=0}^\infty\frac{(-1)^k}{2k+1}x^{2k+1}
	 * 
	 * Diese reihe konvergiert für |x|<=1/2 gar nicht mal soo schlecht
	 */
	
	//iterative version die von vorne aufaddiert 
	//dient nur der demonstration, dass es andersherum besser geht
	public static double series_atan_iterative(double x){
		
		//return Math.atan(x);
		double result=0;
		double nominator=x;
		double denominator=1;
		x*=x;
		
		for(int i=0; i<1000; i++){
			result+=nominator/denominator;
			nominator*=-x;
			denominator+=2;
		}
		return result;
	}
	
	//das ist dieselbe reihe von hinten herum aufaddiert. Stimmt fast auf machinengenauigkeit
	public static double series_atan(double x){
		return x+rec(32,x,1,x*x);
	}
	
	public static double rec(int depth, double numerator, double denominator, double xSquare){
		if(depth==0){
			return 0;
		}else{
			numerator*=-xSquare;
			denominator+=2;
			return numerator/denominator+rec(depth-1,numerator, denominator, xSquare);
		}
	}
	
	//der knackpunkt: CORDIC für arkustangens für rechte halbebene
	public static double cordic_atan2(double y, double x){
		boolean[] direction=new boolean[N];
		double newX;
		double pow2=1;
		//hin und herdrehen, drehrichtungen abspeichern
		for(int i=0; i<N; i++,pow2/=2){
			direction[i]=(y<0); //wenn y<0, dann nach links drehen, ansonsten nach rechts
			if(direction[i]){
				newX=x-pow2*y;
				y=pow2*x+y;
				x=newX;
			}else{
				newX=x+pow2*y;
				y=-pow2*x+y;
				x=newX;
			}
		}
		//winkel der teildrehungen entsprechend den richtungen aufaddieren
		//um rundungsfehler zu vermeiden beim letzten beginnen!
		double result=0;
		for(int i=N-1; i>=0; i--){
			if(direction[i]){
				result-=angles[i];
			}else{
				result+=angles[i];
			}
		}
		
		return result;
	}
	
	//anwendungen auf weitere funktionen
	//Arkuskosinus für positive werte. 
	//Alles andere errechnet sich durch fallunterscheidungen und +-PI
	public static double cordic_acos(double x){
		return cordic_atan2(Math.sqrt(1-x*x),x);
	}
	
	public static void main(String..._){
		System.out.println("Referenzwert, " +
				"Reihe(von rechts aufsummiert), " +
				"Reihe(von links aufsummiert) für den kritischsten wert 0.5 im Vergleich:");
		System.out.println(Math.atan(0.5)+" "+series_atan(0.5)+" "+series_atan_iterative(0.5));
		System.out.println("\n");
		
		System.out.println("test von atan2 implementierung mit CORDIC für zufällige werten x,y");
		System.out.println("x\t\t\ty\t\t\tMath\t\t\tCORDIC\t\t\tFehler");
		for(int i=0; i<10; i++){
			double y=Math.random()*2-1;
			double x=Math.random();
			double math=Math.atan2(y,x);
			double cordic=cordic_atan2(y,x);
			double error=Math.abs(math-cordic);
			System.out.println(x+"\t"+y+"\t"+math+"\t"+cordic+"\t"+error);
		}
		
		System.out.println("\n");
		System.out.println("test von acos implementierung mit CORDIC für zufällige werten x>0");
		System.out.println("x\t\t\tMath\t\t\tCORDIC\t\t\tFehler");
		for(int i=0; i<10; i++){
			double x=Math.random();
			double math=Math.acos(x);
			double cordic=cordic_acos(x);
			double error=Math.abs(math-cordic);
			System.out.println(x+"\t"+math+"\t"+cordic+"\t"+error);
		}
	}
}
```
Ark, hast du nicht zufälligerweise irgendein kleines Interface und ein testprogrammchen gebastelt, mit dem man verschiedene Berechnungsmethoden vergleichen könnte? Dort wo sie konvergiert, scheint die Reihe eigentlich auch gar nicht mal so schlecht zu sein.


----------



## 0x7F800000 (26. Okt 2009)

Mit einer kleiner Verspätung liefere ich dann mal die angeforderte Implementierung für die Rückrichtung: die Funktion, die zu einem Winkel gleichzeitig sin und cos berechnet (heißt [c]cordic_cos_sin[/c]).

```
import static java.lang.System.*;
import static java.lang.Math.*;

public class CORDIC {
	
	public static final int N=64;
	public static double[] angles;
	public static double K;
	static{
		//einmalige initialisierung, kann solange dauern wie sie will, 
		//daher können lahme reihenentwicklungen verwendet werden
		angles=new double[N];
		double pow_2=1;
		K=1;
		
		for(int i=0; i<N; i++, pow_2/=2){
			angles[i]=series_atan(pow_2);
			if(i>0) K*=series_cos(angles[i]);
		}
		
		//bekannte werte im bereich wo es schlecht konvergiert per hand nachbessern
		angles[0]=Math.PI/4;
		K*=series_cos(Math.PI/4);
	}
	
	/*
	 * lahme implementierung von Arkustangens
	 * Die reihe erhält man, indem man die ableitung von arkustangens betrachtet
	 * diese ist 1/(1+x^2)
	 * die Taylorreihe von 1/(1+z) lässt sich leicht bestimmen
	 * darein setzt man z=x^2 ein
	 * auf [-1,1] konvergiert die reihe gleichmäßig, also darf man zum aufleiten das 
	 * Integral mit der summe vertauschen
	 * Am ende erhält man 
	 * 
	 * \atan(x)=\sum_{k=0}^\infty\frac{(-1)^k}{2k+1}x^{2k+1}
	 * 
	 * Diese reihe konvergiert für |x|<=1/2 gar nicht mal soo schlecht
	 */
	
	//iterative version die von vorne aufaddiert 
	//dient nur der demonstration, wie scheiße die ist^^
	public static double series_atan_iterative(double x){
		
		//return Math.atan(x);
		double result=0;
		double nominator=x;
		double denominator=1;
		x*=x;
		
		for(int i=0; i<1000; i++){
			result+=nominator/denominator;
			nominator*=-x;
			denominator+=2;
		}
		return result;
	}
	
	//das ist dieselbe reihe von hinten herum aufaddiert. Stimmt fast auf machinengenauigkeit
	public static double series_atan(double x){
		return x+rec(32,x,1,x*x);
	}
	
	public static double rec(int depth, double numerator, double denominator, double xSquare){
		if(depth==0){
			return 0;
		}else{
			numerator*=-xSquare;
			denominator+=2;
			return numerator/denominator+rec(depth-1,numerator, denominator, xSquare);
		}
	}
	
	//relativ lahme taylor-reihenentwicklung für Kosinus
	public static double series_cos(double x){
		return 1+cosRec(1,1,1,x*x);
	}
	
	public static double cosRec(int k, double numerator, double denominator, double xSquare){
		if(k==20){
			return 0;
		}else{
			numerator*=-xSquare;
			denominator*=(2*(2*k-1)*k);
			return numerator/denominator+cosRec(k+1,numerator,denominator,xSquare);
		}
	}
	
	//der knackpunkt: CORDIC für arkustangens für rechte halbebene
	public static double cordic_atan2(double y, double x){
		boolean[] direction=new boolean[N];
		double newX;
		double pow2=1;
		//hin und herdrehen, drehrichtungen abspeichern
		for(int i=0; i<N; i++,pow2/=2){
			direction[i]=(y<0); //wenn y<0, dann nach links drehen, ansonsten nach rechts
			if(direction[i]){
				newX=x-pow2*y;
				y=pow2*x+y;
				x=newX;
			}else{
				newX=x+pow2*y;
				y=-pow2*x+y;
				x=newX;
			}
		}
		//winkel der teildrehungen entsprechend den richtungen aufaddieren
		//um rundungsfehler zu vermeiden beim letzten beginnen!
		double result=0;
		for(int i=N-1; i>=0; i--){
			if(direction[i]){
				result-=angles[i];
			}else{
				result+=angles[i];
			}
		}
		
		return result;
	}
	
	//anwendungen auf weitere funktionen
	//Arkuskosinus für positive werte. 
	//Alles andere errechnet sich durch fallunterscheidungen und +-PI
	public static double cordic_acos(double x){
		return cordic_atan2(sqrt(1-x*x),x);
	}
	
	//alles nochmal andersherum:
	//cos und sin zu einem winkel berechnen
	public static double[] cordic_cos_sin(double angle){
		boolean[] direction=new boolean[N];
		double newX;
		double pow2=1;
		
		//den winkel in vorberechnete teilwinkel zerlegen, drehrichtungen abspeichern
		double approximation=0;
		for(int i=0; i<N; i++){
			if(angle>approximation){
				direction[i]=true;
				approximation+=angles[i];
			}else{
				direction[i]=false;
				approximation-=angles[i];
			}
		}
		
		//entsprechend den abgespeicherten drehrichtungen hin und herdrehen
		double x=1, y=0;
		for(int i=0; i<N; i++,pow2/=2){
			if(direction[i]){
				newX=x-pow2*y;
				y=pow2*x+y;
				x=newX;
			}else{
				newX=x+pow2*y;
				y=-pow2*x+y;
				x=newX;
			}
		}
		return new double[]{K*x, K*y};
	}
	
	
	
	public static void main(String..._){
		out.println("Referenzwert, " +
				"Reihe(von rechts aufsummiert), " +
				"Reihe(von links aufsummiert) für den kritischsten wert 0.5 im Vergleich:");
		out.println(atan(0.5)+" "+series_atan(0.5)+" "+series_atan_iterative(0.5));
		out.println("\n");
		
		out.println("test von atan2 implementierung mit CORDIC für zufällige werte x,y");
		out.println("x\t\t\ty\t\t\tMath\t\t\tCORDIC\t\t\tFehler");
		for(int i=0; i<10; i++){
			double y=random()*2-1;
			double x=random();
			double math=atan2(y,x);
			double cordic=cordic_atan2(y,x);
			double error=abs(math-cordic);
			out.println(x+"\t"+y+"\t"+math+"\t"+cordic+"\t"+error);
		}
		
		out.println("\n");
		out.println("test von acos implementierung mit CORDIC für zufällige werte x>0");
		out.println("x\t\t\tMath\t\t\tCORDIC\t\t\tFehler");
		for(int i=0; i<10; i++){
			double x=random();
			double math=acos(x);
			double cordic=cordic_acos(x);
			double error=abs(math-cordic);
			out.println(x+"\t"+math+"\t"+cordic+"\t"+error);
		}
		
		out.println("\n");
		out.println("test der Taylorreihe für cos");
		out.println("x\t\t\tMath\t\t\ttaylor\t\t\tFehler");
		for(int i=0; i<10; i++){
			double x=random();
			double math=cos(x);
			double taylor=series_cos(x);
			double error=abs(math-taylor);
			out.println(x+"\t"+math+"\t"+taylor+"\t"+error);
		}
		
		out.println("\n");
		out.println("test von x->(cos x,sin x) implementierung mit CORDIC für zufällige winkeln x");
		out.println("x\t\t\tMath\t\t\tCORDIC\t\t\tFehler");
		for(int i=0; i<10; i++){
			double x=random()*0.7;
			double mathX=cos(x) , mathY=sin(x);
			double cordX=cordic_cos_sin(x)[0], cordY=cordic_cos_sin(x)[1];
			double error=hypot(mathX-cordX, mathY-cordY);
			out.printf("%1.8f\t(%1.8f,%1.8f)\t(%1.8f,%1.8f)\t%1.8e\n",x,mathX,mathY,cordX,cordY,error);
		}
	}
}
```
Die zusätzliche Funktion habe ich einfach in den alten code eingefügt.

Prinzipiell ist nichts neues dazugekommen: die Implementierung ist mehr oder weniger aus Wikipedia übernommen, sogar die Konstante "K" habe ich genauso benannt. Die Erklärung dort fand ich nachvollziehbar, aber bei Bedarf kann ich irgendwelche speziellen Schritte evtl. genauer erläutern.


----------



## Ark (26. Okt 2009)

Vielen, vielen Dank, 0x7F800000. Das wird mir wohl sehr weiterhelfen.  Ich schaue mir noch einmal die Erklärung in der Wikipedia an und hoffe, dass ich mit Hilfe des Codes noch einigermaßen schlau daraus werde. :rtfm:

(Oh, Mann, ich glaube, wenn ich zu studieren anfange, werde ich fachlich bestens vorbereitet sein. )

Ark


----------



## schalentier (26. Okt 2009)

Ark, du hast noch nix zur Genauigkeit gesagt, aber prinzipiell muesste doch auch eine einfache HashMap (Double->Double) reichen, die du am Anfang je nach benoetigter Genauigkeit befuellst, oder? Des is zumindest extrem einfach und tierisch schnell ;-)


----------



## 0x7F800000 (26. Okt 2009)

```
public static void sin(double x){
   if(abs(x%(2*PI))>PI/2) return 2/PI; else return -2/PI;
}
```
passt so ungefähr^^


----------



## Ark (27. Okt 2009)

schalentier hat gesagt.:


> Ark, du hast noch nix zur Genauigkeit gesagt, aber prinzipiell muesste doch auch eine einfache HashMap (Double->Double) reichen, die du am Anfang je nach benoetigter Genauigkeit befuellst, oder? Des is zumindest extrem einfach und tierisch schnell ;-)


Jupp, da gibt's nur zwei Probleme:

1. Zum Befüllen der Arrays benötige ich die Funktionen, die mir sin, asin etc. berechnen, die habe ich aber bei meinem Zielsystem noch nicht. 
2. Zur benötigten Genauigkeit ist nichts bekannt, weshalb z.B. für Sinus zumindest der Bereich von 0 bis PI/2 abgedeckt sein muss. Das bringt also auch nicht wirklich weiter.

Ark


----------



## Ark (27. Okt 2009)

Okay, ich habe mir noch mal die Wikipedia zu Gemüte geführt. Was ich bisher wie verstanden (oder vllt. sogar missverstanden) habe:


In cordic_cos_sin() wird in der ersten Schleife nur der eingegebene Winkel als Linearkombination der vorher berechneten Teilwinkel dargestellt bzw. approximiert.
Dass du beide Male die die Drehrichtungen abspeicherst, um sie anschließend "rückwärts" zu verwenden, ist allein dazu da, die Genauigkeit möglichst hoch zu halten. Die Berechnung hätte also genausogut auch schon in der jeweils ersten Schleife durchgeführt werden können.
Was ich z.B. noch nicht verstehe, ist die Initialisierung und überhaupt der Ansatz in der Wikipedia, [c]tan(alpha_i) = 2^(-i)[/c]. Wie kommt man auf so was?

Und: Handelt es sich bei der Initialisierung bloß um die Ermittlung von Konstanten, die man aus den Schleifen der eigentlichen Funktionen herausgezogen hat, weil sie invariant sind (um z.B. nur die Berechnung zu beschleunigen)? Wenn ja: Wie würde z.B. cordic_cos_sin() aussehen, wenn man die Berechnung dieser Konstanten wieder in die Schleifen einarbeiten würde? (Die Frage stelle ich in der Hoffnung, dass sich das Ganze dann für mich verständlicher darstellt.)

Ark


----------



## 0x7F800000 (27. Okt 2009)

Ark hat gesagt.:


> In cordic_cos_sin() wird in der ersten Schleife nur der eingegebene Winkel als Linearkombination der vorher berechneten Teilwinkel dargestellt bzw. approximiert.


schärfer: in dieser "Linearkombination" dürfen nur Faktoren +1 und -1 auftreten, ansonsten stimmt's alles nicht mehr.


> Dass du beide Male die die Drehrichtungen abspeicherst, um sie anschließend "rückwärts" zu verwenden, ist allein dazu da, die Genauigkeit möglichst hoch zu halten. Die Berechnung hätte also genausogut auch schon in der jeweils ersten Schleife durchgeführt werden können.


Ja. Schöner wäre es, beide methoden in rekursiver Form umzuschreiben: dann wäre es eleganter und genauer, aber jetzt habe ich das so gelassen.



> Was ich z.B. noch nicht verstehe, ist die Initialisierung und überhaupt der Ansatz in der Wikipedia, [c]tan(alpha_i) = 2^(-i)[/c]. Wie kommt man auf so was?


Es geht einfach nur darum, die Winkeln so zu wählen, dass alle Drehmatrizen nur noch die Einträge 1 und 2^-i enthalten. Dann kann man damit wesentlich schneller rumrechnen, weil nur Shift's erforderlich sind.



> Und: Handelt es sich bei der Initialisierung bloß um die Ermittlung von Konstanten, die man aus den Schleifen der eigentlichen Funktionen herausgezogen hat, weil sie invariant sind (um z.B. nur die Berechnung zu beschleunigen)?


Ja.


> Wenn ja: Wie würde z.B. cordic_cos_sin() aussehen, wenn man die Berechnung dieser Konstanten wieder in die Schleifen einarbeiten würde? (Die Frage stelle ich in der Hoffnung, dass sich das Ganze dann für mich verständlicher darstellt.)


Äußerst furchtbar. Dann würde man, für einen einzigen Kosinus-wert fürnfzig mal Arkustangens und Kosinus für irgendwelche merkwürdigen werte ausrechnen, die nichts mit der Eingabe zu tun haben. Wenn man diese speziellen Werte nicht vorher berechnet, verliert diese Konstruktion ihre Daseinsberechtigung: dann kann man gleich die Reihe nehmen, und an der richtigen Stelle auswerten.

Die Grundidee ist ja wie folgt:
Man hat ein Problem: man will den Zusammenhang zwischen dem Winkel und den Sinus/Kosinus-Werten herstellen.

Man kann dieses Problem direkt lösen, indem man die Reihen auswertet (dies ist aber langsam).

Bei CORDIC stellt man diesen Zusammenhang für ganz wenige, ganz spezielle Werte (die Winkeln [c]arctan(2^-i)[/c]) mithilfe der Reihen (oder sonstiger langsamer Verfahren) her, und speichert die Ergebnisse in einer Tabelle ab (hier nennt sich diese Tabelle [c]angles[/c]). Dann ist das Problem für diese speziellen Werte gelöst. Was ist an diesen Werten so speziell? Diese Werte sind deshalb so gewählt, weil sich daraus sehr einfach Lösungen für alle anderen Werte kombinieren lassen: beliebige Winkeln lassen sich als "+-1-Linearkombination" von [c]angles[/c] darstellen, während die dazugehörigen Drehmatrizen aufmultipliziert werden.
Zum Darstellen des Winkels muss man nur addieren können, zum multiplizieren der Matrizen muss man nur bitshifts & addition können. Das ist (verglichen zur Auswertung der Reihen mit vielen Multiplikationen & teueren Divisionen) auf bestimmten FPU's sehr viel schneller, da man praktisch ohne Multiplikationen auskommt, sondern nur addiert & shiftet. Aber nicht nur auf FPU's: das Verfahren ist an sich besser, da es schneller als Reihen konvergiert, und numerisch stabiler ist.


----------



## Ark (31. Okt 2009)

Irgendwie erinnert mich das an die Logarithmen, die sich ja lediglich durch konstante Faktoren voneinander unterscheiden. Ob sich diese Denkweise irgendwie darauf adaptieren lassen?

Ansonsten: Irgendwie bin ich wohl gerade zu dumm, um atan2() für alle Quadranten richtig (nach Math) zu implementieren:

```
public static double atan2(double y,double x){
	return x>=0 ? cordic_atan2(y,1):// ja, wie eigentlich weiter?
}
```
Bei Sinus und Kosinus habe ich das ja hingekriegt, aber hier tue ich mich irgendwie schwer. Irgendwie komme ich mir gegenüber den mathematischen Leuchten hier total ungebildet vor. xD

Ark

(Irgendwie sind hier viele "irgendwies" in diesem Beitrag. )


----------



## 0x7F800000 (1. Nov 2009)

Ark hat gesagt.:


> Irgendwie erinnert mich das an die Logarithmen, die sich ja lediglich durch konstante Faktoren voneinander unterscheiden. Ob sich diese Denkweise irgendwie darauf adaptieren lassen?


Öhm... Nja, alle Funktionswerte vom klassischen log sind reelle Zahlen, und zwei reelle Zahlen unterscheiden sich immer gewissermaßen um einen konstanten Faktor... Ich verstehe die Aussage nicht. Aber Logarithmen kann man mit einem ähnlichen Verfahren ("anderem CORDIC-Modus") auch ausrechnen. 



> Ansonsten: Irgendwie bin ich wohl gerade zu dumm, um atan2() für alle Quadranten richtig (nach Math) zu implementieren:




```
public static double atan2(double y, double x){
		return x>=0?cordic_atan2(y,x):(y>=0?(PI-cordic_atan2(y,-x)):(-PI+cordic_atan2(-y,-x)));
	}
```



> Irgendwie komme ich mir gegenüber den mathematischen Leuchten hier total ungebildet vor. xD



Du weißt was eine Drehmatrix ist
Du weißt wie man Matrizen multipliziert
Du weißt welche geometrische Bedeutung der Kosinus eines Winkels hat
mehr brauchst du wirklich nicht. Das hat nichts mit "ungebildet" zu tun, für dieses Verfahren benötigt man lediglich etwas elementargeometrische Anschauung, und den Mut, die beschreibung des Algos am Stück durchzulesen und nachzuvollziehen. Du musst daran glauben, dass es einfach ist, da ist kein Rocketscience drin!


----------

