Wurzel ziehen in C

[Gollum]

Hi wollt fragen ob jemand von euch ahnung hat wie ich nen algorithmus schreibe um eine wurzel zu ziehen ? also kein standartbefehl aus c sonder über mathematisches näheren !

 

[cmk]

also ich kann dir leider nur sagen wie du es theorethisch machen kannst, weil ich im syntax von c noch nicht so fit bin.

also:

wenn du eine wurzel ² nimmst (also die wurzel mit sich selbst mulitplizierst) bekommst du die zahl, von der man immer ausgeht.

Man sagt ja - "wie ist die wurzel aus 25" - also

wenn du die wurzel aus 25 haben willst musst du folgendes machen (natürlich dynamisch)

du durchläufst eine for schleife solange, bis die zahl, die beim durchlaf erhöht wird mit sich selbst multipliziert die ausgangszahl ergibt.

zb.
float i = 0.00000000001;
for(i*i != 25)
{
i = i + 0.00000000001;
}

also:

i ist die variable, die bei jedem durchgang um 0.00000000001 erhöht wird. und solange 0.00000000001² nicht 25 ist wird 0.00000000001 immer wieder im 0.00000000001 erhöht.

ist zwar sehr systemlastig aber müsste funzen wenn du keine andren funktionen nutzen willst

hehe hoffe ich habe geholfen!

 

[Andre]

sollte so bei integers funktiorieren...
aber hab nicht getestet

int zahl; 
int wurzel ;   
 cin >> zahl 
for (int c = 1; c < zahl; c++)  {
 if( zahl % c == 0)  {
        if(c*c == zahl)  
             wurzel = c ;   } 
                         }     
                  cout << wurzel  ;  
     }

###########edit###########
ups..war zu langsam

 

[JoelH]

include <iostream>
using namespace std;

double sqrt(double habenwill)
{
	    int counter = 0;
		double spanne = habenwill;
		double grenze = spanne/2;
		double istes  = spanne*spanne;
		while (istes != habenwill)
		{
			if (istes < habenwill)
			{
				spanne = spanne + grenze;
			}
			else 
			{
				spanne = spanne - grenze;
				grenze /= 2;
			}
			counter++;
			istes = spanne*spanne;
			cout << spanne << " * " << spanne << " = " << istes << "              " << counter << endl;
		}
		return spanne;
}

int main (void)
{
	double suche;
	cin >> suche;
	cout << endl << sqrt(suche) << endl;
	return 0;
}

so sollte das gehen, leider bricht er nicht ab, ist auch C++ (Stream) aber das ist ja sekundär. Probier es einfach mal aus. Wie kann man eigentlich nur die ersten x Ziffern miteinander vergleichen ?

 

[JoelH]

hmm,

@FUSEL
Das ist äusserst ineffiziert !

 

[cmk]

hmmmmmmm

andres beispiel ist dann auch ineffizient. ich habe es halt nur genauer gemacht. man kann den float ja auch auf 1.0 setzen dann isses genauso wie andres beispiel auch.

bei mir hat man halt mehr kontrolle

klar is meines keine gute lösung aber ich habe versucht zu helfen und das zählt-

 

[Andre]

andres beispiel ist dann auch ineffizient.

neeee mein Beispiel ist scheisse

bei mir hat man halt mehr kontrolle

da hasste recht!

aber ich habe versucht zu helfen und das zählt-

genau

glaub nich da joelH das böse gemeint hat...
ist doch gut wenn einer konstruktiv kritisieren kann..da lern man wenigstens was...

 

[cmk]

ja klar - kritik is gut ich weiß dass joehl das net böse gemeint hat aber ich wollte nur darauf hinweise dass ich nicht alleine ein ineffizientes beispiel gebracht habe ich habe das auch nicht böse gemeint

 

[JoelH]

#include <iostream>
using namespace std;


const double epsilon = 1e-5;

bool isEqual(double a, double b)
{
   return abs(a - b) < epsilon;
}

double sqrt(double habenwill)
{
	    int counter = 0;
		double spanne = habenwill;
		double grenze = spanne/2;
		double istes  = spanne*spanne;
		while (!isEqual(istes,habenwill))
		{
			if (istes < habenwill)
			{
				spanne = spanne + grenze;
			}
			else 
			{
				spanne = spanne - grenze;
				grenze /= 2;
			}
			counter++;
			istes = spanne*spanne;
			cout << spanne << " * " << spanne << " = " << istes << "              " << counter << endl;
		}
		return spanne;
}

int main (void)
{
	double suche;
	cin >> suche;
	cout << endl << sqrt(suche) << endl;
	return 0;
}

So jetzt geht auch die Abbruchbedingung

@FUSEL
Das war nicht böse gemeint, nur ein Tip Nehmen wir mal meinen Code der löst die Wurzel aus 8 in 48 Interationen, wieviele braucht wohl deiner ? Wenn man davon ausgeht dass du auf 5 Stellen testest und bei 0 anfangst und bis 2.8xxx zählst sind das 28000 iterationen , also ca. 28000 mehr als meine Funktion braucht, das meinte ich eigentlich.

 

[cmk]

ja

du kannst jetzt gift drauf nehmen, dass ich mir sobald mein linxu wieder komplett läuft ich versuche das zu verstehen was du da an code geschrieben hast

also ich sage auch danke und wäre froh wenn du es noch auskommentieren würdest (muss nicht heut sein da mein pc noch net läuft )

 

[JoelH]

hmm,

ist ganz einfach, ich nehme einfach an das x * x = y ist , wobei y gesucht wird.

ist x * x < y addiere ich einfach einen kleinen Betrag zu x dazu, das ist die Variable grenze. Diese setze ich zu beginn auf einen beliebigen Wert < x . Wenn jetzt aber x * x > y ist dann ziehe ich die grenze wieder ab und verkleinere die grenze um die hälfte um sie dann wieder zu x dazu zu zählen. So tendiert grenze gegen 0 und der Wert x wird immer genauer bis er trifft. natürlich nur so genau wie der Computer das berechenen kann.
zB. hier die Iterationen wbis er auf die Qurzel von acht kommt, da sieht man es glaub ich recht gut :

4 * 4 = 16 1
2 * 2 = 4 2
3 * 3 = 9 3
2 * 2 = 4 4
2.5 * 2.5 = 6.25 5
3 * 3 = 9 6
2.5 * 2.5 = 6.25 7
2.75 * 2.75 = 7.5625 8
3 * 3 = 9 9
2.75 * 2.75 = 7.5625 10
2.875 * 2.875 = 8.26562 11
2.75 * 2.75 = 7.5625 12
2.8125 * 2.8125 = 7.91016 13
2.875 * 2.875 = 8.26562 14
2.8125 * 2.8125 = 7.91016 15
2.84375 * 2.84375 = 8.08691 16
2.8125 * 2.8125 = 7.91016 17
2.82812 * 2.82812 = 7.99829 18
2.84375 * 2.84375 = 8.08691 19
2.82812 * 2.82812 = 7.99829 20
2.83594 * 2.83594 = 8.04254 21
2.82812 * 2.82812 = 7.99829 22
2.83203 * 2.83203 = 8.0204 23
2.82812 * 2.82812 = 7.99829 24
2.83008 * 2.83008 = 8.00934 25
2.82812 * 2.82812 = 7.99829 26
2.8291 * 2.8291 = 8.00382 27
2.82812 * 2.82812 = 7.99829 28
2.82861 * 2.82861 = 8.00105 29
2.82812 * 2.82812 = 7.99829 30
2.82837 * 2.82837 = 7.99967 31
2.82861 * 2.82861 = 8.00105 32
2.82837 * 2.82837 = 7.99967 33
2.82849 * 2.82849 = 8.00036 34
2.82837 * 2.82837 = 7.99967 35
2.82843 * 2.82843 = 8.00002 36
2.82837 * 2.82837 = 7.99967 37
2.8284 * 2.8284 = 7.99984 38
2.82843 * 2.82843 = 8.00002 39
2.8284 * 2.8284 = 7.99984 40
2.82841 * 2.82841 = 7.99993 41
2.82843 * 2.82843 = 8.00002 42
2.82841 * 2.82841 = 7.99993 43
2.82842 * 2.82842 = 7.99997 44
2.82843 * 2.82843 = 8.00002 45
2.82842 * 2.82842 = 7.99997 46
2.82843 * 2.82843 = 8 47

 

[cmk]

danke joehl

 

[JoelH]

hmm,

kein Problem, der Algo ist auch garnicht von mir, der ist schon so alt wie die alten Griechen, frag mich aber nicht von wem er ist, dass weiss ich auch nicht, aber das ist so der klassische Näherungsalgo. Wird sehr oft benutzt da er sehr schnell ist. zB. auch bei suchalgos in sortierten Arrays oder Quicksort arbeitet auch irgendwie in dieser Art usw.

 

[saintjoe]

Warum so kompliziert?
Eine Wurzel zu ziehen ist doch nix anderes als:
x=y^0.5
In PHP ginge das wurzel ziehen z.B. mit:

$x = pow($y,0.5);

In C sollte das denke ich auch recht einfach zu realisieren sein...

MfG

 

[cmk]

stimmt nicht.

x = y * 0.5

angenommen

y = 16

jeder weiß dass die wurzel aus 16 4 ist.

aber

16 * 0.5 = 8

und 8 * 8 = 64

denkfehler 0 punkte setzten 6.

außerdem wollte er keine spezielle funktion anwenden.

 

[JoelH]

hmm,

@saintjoe
Dann hätte er auch gleich die sqrt() aus der math.h nehmen können Das wollte er aber nicht !!

@FUSEL
Falsch, du bist im unrecht weil du dich verlesen hast, 2^0.5 hat saintjoe geschrieben nicht 2*0.5 das ist was anderes !!!

 

[saintjoe]

Original geschrieben von FUSEL

denkfehler 0 punkte setzten 6.

Genau, setz dich mal hin

 

[cmk]

*schäm*

 

[LiquidAcid]

Da ich hier noch kein "carmackschen" Code gesehen habe, poste ich den jetzt mal. Naja, wenigstens ein Link dazu.

Link

Thema ist fast inverse squareroot via Newton-Iteration. Interessant ist aber vorallem die Berechnung des Startwertes.

cya
liquid

 

[shorty0802]

Ja ich hab des so gelernt.

Also in der Schule lernt man des mit dem Heron Verfahren. Is eigetlich ziemlich einfach. Ist bei wikipedia gut nachzulesen. Ich würd des dann so ungefähr machen:

#include<iostream>
using namespace std;

int main()
{
int count=0;
int naeherungswert=1;
int wurzel=25;
while(count<5)
{
count++;
naeherungswert=(naeherungswert+wurzel/naeherungswert)/2;

}
cout<<naeherungswert;
system("pause");
}

Also ich habe jetz integer genommen um auf das Runden zu verzichten aber um richtige wurzel herauszubekommen, also nicht nur von 9, 16,25 braucht man float. Und wenn man es genauer haben will muss man nur die Schleifendurchläufe (count) erhöhen.