Phytagoras ohne math.h

Page 1 of 2

01/08/2013 06:55 Kosic#1

Hey Leute,

Ich hab mich nochmal an meinen "mini Rechner" gesetzt und festgestellt dass unter anderem die Phytagoras-Berechnung fehlt. Wollte das ganze ohne den math.h machen.

Schaut daweil so aus:

PHP Code:


			
case '5': //Phytagoras c^2 = a^2 * b^2
            const double j = 0.00000000001;
            double i; 
            buffer = ( zahl1 * zahl1 ) * ( zahl2 * zahl2 );
            std::cout << "Ergebnis: c^2 = " << buffer << std::endl;
            for( i = 0.00000000001; i * j != buffer; )
            {
                i = j + i;
            }
            erg = i;
            std::cout << "Ergebnis: c = " << erg << std::endl;
            break;

Da diese Methode aber zu viel Zeit und Performance in anspruch nimmt, m�chte ich fragen ob wer eine andere Idee hat.

Mfg,
Kosic

01/08/2013 10:09 Nightblizard#2

Naja, du k�nntest inline ASM nutzen und das Zeug somit berechnen.

Code:

int main()
{
	auto a = 2 * 2;
	auto b = 3 * 3;
	auto c = a * b;
	double c_root = 0.0f;

	__asm
	{
		fild c;
		fsqrt;
		fst c_root;
	}
}

Ist jedoch ziemlich unflexibel und l�sst sich nur mit vergleichbar viel Aufwand erweitern. Abgesehen davon ist das der totale Overkill! Was spricht gegen math.h?

01/08/2013 10:12 xNopex#3

Ich w�rde vorschlagen, du verwendest das Heron - Verfahren. Ich habe das gerade mal getestet mit 10 Iterationsschritten. Funktioniert sehr sch�n.

01/08/2013 15:53 MrSm!th#4

Ansonsten gibt es f�r sin, cos, sqrt und Konsorten afaik auch gute N�herungspolynome. Muss es denn so derma�en exakt sein, dass du in deiner Schleife so kleinschrittig vorgehst? Nicht umsonst rechnen Physiker nicht genauer, als sie messen k�nnen :p

01/08/2013 21:28 xNopex#5

N�herungspolynome sind eher ungeeignet. Man entwickelt hier um einen bestimmten Punkt und erh�lt dann f�r genau diesen Punkt genaue Ersatzpolynome. Werte, die weiter weg von diesem Punkt liegen kriegen einen mehr oder weniger gro�en Fehler mit. Das h�ngt zum einem vom Grad des Ersatzpolynoms ab zum anderen kommts auch wirklich drauf an, wie weit weg man vom Entwicklungspunkt ist. Iterationsverfahren sind hier weitaus komfortabler.
Bei Sinus (und cos dann auch) verh�lt sich das nochmal anders. Hier herrscht eine engere Verbindung zur e-Funktion, sprich man kann einen sinus 1:1 in eine Kombination aus e-Funktionen �bersetzen. Zum programmieren hilft das allerdings auch nicht wirklich weiter.
Ich werbe an dieser Stelle nochmal f�r das Heronverfahren ;O

01/08/2013 23:07 nkkk#6

w�rde dir auch Heronverfahren nahelegen

01/09/2013 06:24 Kosic#7

Wenn ichs richtig verstanden habe, m�sste es doch so aussehen, oder?( Der erste N�herungsversuch) den Zweiten probiere ich heute Nachmittag.

Code:

        buffer = ( zahl1 * zahl1 ) * ( zahl2 * zahl2 );
	std::cout << "Ergebnis: c^2 = " << buffer << std::endl;
			
	buffer2 = ( buffer + 1 ) / 2;
	buffer3 = buffer / buffer2;
	buffer4 = ( buffer2 + buffer3 ) / 2;


	erg = buffer4;
	std::cout << "Ergebnis: c = " << erg << std::endl;

01/09/2013 09:42 snow#8

Machs doch mit Rekursion? Da ist das Heron-Verfahren doch ideal daf�r..

x(n + 1) = (x(n) + a / x(n)) / 2 -> x(n) = (x(n - 1) + a / x(n - 1)) / 2

Als Code:

Code:

double x(n, a)
{
    double y = (n == 0) ? a : x(n - 1, a);
    return (y + a / y) / 2;
}

(das war jetzt nur kurz aus dem Kopf raus, kann man garantiert noch optimieren)

Falls du nicht wei�t, wie du das verwenden sollst: erg = x(5, buffer); -> weniger als 5 liefert ein falsches Ergebnis.

Gib Bescheid, ob es klappt. :)

(bestimmt ist das jetzt komplett falsch und voll peinlich. :()

01/09/2013 13:50 Kosic#9

Verstehe deinen Code nicht, snow.

Sorry :S

01/09/2013 14:06 snow#10

Ist dir die Rekursion bekannt? Wenn nein, solltest du es evtl. so machen, wie du es bisher gemacht hast.

Code:

double x(n, a)
{
   double y = 0;

   if (n == 0) // f�r x(0) kann man a nehmen, statt x(n) + a / x(n) k�nnen wir hier also a + a / x einsetzen
       y = a; 
   else 
       y = x(n - 1, a); // y ist das Ergebnis von x(n -1)
return (y + a / y) / 2; // y in die Formel einsetzen
}

Schwierig zu verstehen, das stimmt. :/

�ber eine Iteration ist es evtl. einfacher:

Code:

double wurzel = 0;

for (int i = 0; i < MAX_DURCHLAUF; i++) {

if (i == 0) // wenn es der erste Durchlauf, also x(0) ist
 wurzel =  (buffer + 1) / 2;
else 
 wurzel = (wurzel + buffer / wurzel) / 2; // x(n�chstes) = (x(aktuelles) + a / x(aktuelles)) / 2

}

printf("Die Wurzel von c betr�gt %lf", wurzel);

Keine Ahnung, ob das klappt, hocke hier gerade in der Vorlesung. :)

01/09/2013 14:36 Kosic#11

Habs jetz so gemacht: (Problem solved)

Code:

case '5': //Phytagoras c^2 = a^2 * b^2
		float c2;
		float x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10;
		c2 = ( zahl1 * zahl1 ) * ( zahl2 * zahl2 );
		std::cout << "Ergebnis: c^2 = " << c2 << std::endl;
		
		x0 = ( c2 + 1 ) / 2;

		x1 = ( x0 + ( c2 / x0 ) ) / 2;

		x2 = ( x1 + ( c2 / x1 ) ) / 2;

		x3 = ( x2 + ( c2 / x2 ) ) / 2;

		x4 = ( x3 + ( c2 / x3 ) ) / 2;

		x5 = ( x4 + ( c2 / x4 ) ) / 2;

		x6 = ( x5 + ( c2 / x5 ) ) / 2;

		x7 = ( x6 + ( c2 / x6 ) ) / 2;

		x8 = ( x7 + ( c2 / x7 ) ) / 2;

		x9 = ( x8 + ( c2 / x8 ) ) / 2;

		x10 = ( x9 + ( c2 / x9 ) ) / 2;

		erg = x10;
		std::cout << "Ergebnis: c = " << erg << std::endl;
		break;

01/13/2013 13:56 theitfan1337#12

Quote:

Originally Posted by xNopex

N�herungspolynome sind eher ungeeignet. Man entwickelt hier um einen bestimmten Punkt und erh�lt dann f�r genau diesen Punkt genaue Ersatzpolynome. Werte, die weiter weg von diesem Punkt liegen kriegen einen mehr oder weniger gro�en Fehler mit. Das h�ngt zum einem vom Grad des Ersatzpolynoms ab zum anderen kommts auch wirklich drauf an, wie weit weg man vom Entwicklungspunkt ist. Iterationsverfahren sind hier weitaus komfortabler.
Bei Sinus (und cos dann auch) verh�lt sich das nochmal anders. Hier herrscht eine engere Verbindung zur e-Funktion, sprich man kann einen sinus 1:1 in eine Kombination aus e-Funktionen �bersetzen. Zum programmieren hilft das allerdings auch nicht wirklich weiter.
Ich werbe an dieser Stelle nochmal f�r das Heronverfahren ;O

e-Funktion, trigonometrische Funktionen etc. werden vom Taschenrechner und PC alle �ber Taylor-Reihen berechnet. Die Wurzel kann man dann �ber diese grundlegenden Funktionen ann�hern.

sqrt(x) = exp(1/2* ln(x)) = (exp(ln(x)))^(1/2) = sqrt(exp(ln(x))) = sqrt(x)

Zumindest glaube ich, dass das so gehandhabt wird. Nicht, dass ich sonst alle Mathe-Vorlesungen verschlafen w�rde :-p

01/13/2013 14:26 xNopex#13

Bei Sinus und Co kann ich mir noch vorstellen, dass mit Taylorpolynomen das ganze ausgerechnet wird. Hier gen�gt es ja eine Periode anzun�hern. Werte gr��er 2pi oder kleiner 0 kann man dann immer auf diese Periode abbilden.
Bei "komplexeren" Funktionen bin ich mir nicht ganz sicher. Die zu verwendenden Taylopolynome m�ssten hier schon von h�herer Ordnung sein, um genaue Ergebnisse zu bekommen. Das Heron-Verfahren w�re im Beispiel der Wurzelfunktion imho einfacher und genauer. Aber ich kenne das Problem mit dem Verschlafen..

01/13/2013 14:39 theitfan1337#14

Kommt drauf an was du mit komplexeren Funktionen meinst. Im Prinzip ist es doch meistens m�glich, eine Funktion durch sin, cos, exp oder log anzun�hern. Zu denen kennt man die passenden Reihen-Entwicklungen und somit kann man dann alles in vergleichsweise wenig Iterationsschritten recht genau berechnen.
Wobei mir das Heron-Verfahren eig ganz gut gef�llt. Nur gibt es eben nicht immer f�r jede komplexe Funktion eine so "einfache" Iterationsvorschrift.

01/13/2013 20:19 xNopex#15

Naja im Gegensatz zu sin, cos, etc. die periodisch sind und man deshalb nur eine Periode ann�hern muss, muss man bei ln, e, etc. �ber den gesamten Definitionsbereich ann�hern. Und als Nutzer m�chte ich dann nat�rlich genauso genaue ergebnisse f�r extrem kleine Werte, wie f�r extrem gro�e Werte erhalten. Sprich mein Taylorpolynom m�sste von h�herer Ordnung als die gewohnten ersten zwei Glieder sein, die man so immer mal schriftlich ausrechnet. Ergebnisse auf 9Stellen genau sind meistens genug. Das schafft auch mein Taschenrechner. Jetzt m�sste man eben ausrechnen, bis zur welchen Ordnung man entwickeln muss. Mein Gef�hl sagt mir, dass das nicht wenig sein wird.
Den Aufwand k�nnte man sich eben durch z.b. ein Heron Verfahren sparen.

Page 1 of 2