Ungefähres Wurzelziehen ohne Kommazahlen?

TheToast

Hi,

ich brauch für ein Programm auf meinem Handy eine ungefähre Wurzel aus einer Zahl, allerdings ist das Handy nicht das nueste, unterstützt also keine Kommazahlen, somit hat es auch keine Wurzelfunktion.

Jetzt will ich mir eine selbst schreiben, aber ich hab überhaupt keinen Ansatz (die Ganzzahl reicht mir, also reicht es Vollkommen -> Wurzel 10 = 3)

Was mach ich nu?

geloescht

such mal nach "heronsches Näherungsverfahren", ich weiß aber nicht, wie gut es fnktioniert, wenn man nur ganzzahlen darstellen kann.
geloescht

sbrog

ich würde das ungefähr so machen :

int wurzel(int zahl)
{
int i=1;

while (i*i < zahl  )
{
i=i+1 ;
}

return i;

}

leech

@sborg:

was ist denn, wenn du nun als zahl zum Beispiel 80 eingibst?

dein ergebnis:

8 * 8 = 64...

also wäre die wurzel aus 80 bei dir 8...
das richtige ergebnis ist ja: 8.944
-> eine abweichung von 8.944 - 8 = 0.944

wäre es nicht sinnvoller dann intern die Zahl aus 81 zu ziehen und dann als ergebnis 9 auszugeben?

dan wäre die abweichung "nur":

9 - 8.944 = 0.056

also:

dein verfahren ist recht ungenau bei höheren zahlen!

sbrog

ja, schon, das da oben sollte auch nur ein pseudocode beispiel sein. Den "Feinausschliff" wollte ich TheToast selbst überlassen.

camper

wie wäre es damit

int wurzel(int zahl)
{
    if( zahl < 0 ) return -1;  // eventuell auch zahl = -zahl; je nach kontext
    int low = 0, high = zahl, median;
    while( high - low > 1 )
    {
        median = ( low + high ) / 2;
        if( median * median <= zahl ) low = median; else high = median;
    };
    return ( low * ( low + 1 ) >= zahl ) ? low : high;
}

das löst das rundungsproblem und ist für zahlen >> 25 auch schneller.

TheToast

Eine Abweichung bis zu 1 ist absolut in Ordnung für mich, hauptsache das ganze geht schnell, Abweichung von 0.94 ist also in Ordnung und die Methode scheint mir auch so noch die schnellste...

wasiliy

var w,x,y,z : int;
input x;
z := 0; w := 1; y := 1;
  while w <= x do
    z := z + 1;
    w := w + y + 2; 
    y := y + 2;
  od
output z

also nochmal der pseudocode in java umgesetzt [mal die java tags testen =p ]:

public class sqrt {
   public static void main(String[] args) {
     int x = Integer.parseInt(args[0]);
     int z = 0, w = 1, y = 1;

       while (w <= x) {
         z++;
         w = w+y+2;
         y +=2;
       }
     System.out.println(z);
   }
}

Ich kenn mich jetzt nich so gut aus aber wie wäre es hiermit:

int a;
	cin>>a;
	double b=sqrt(a);
	cout<<endl <<setprecision(0) <<b;

otze

sqrt ist nicht schnell

ok, wenn du das sagst, aber geht es nich sowieso bloß um sekundenbruchteile

dEUs

Les einfach nochmals den Ursprungspost ...

Was ich nicht ganz nachvollziehen kann, also dien Handy ist nicht das neueste und kann keine kommazahlen. Jetzt brauchst du für ein programm auf dem handy die Wurzel. Welches Programm auf einem älteren Handy braucht die Eingabe einer Wurzel?
Dann möchtest du selbst eines schreiben, oki. Und dann? die .exe auf dein altes Handy packen? Oder hast du nur einen Algorithmus gesucht, damit du bei deinem Handy die Zahlen(ohne komma ) eingibst und dan ungefähre Ergebnis hast.
Was noch schneller geht. Kauf dir n billiges Handy, dass kann auch Komma dann. Oder geh zur nächsten Bank oder so und frag nach einem kleinen Werbe-Taschenrechner. Nimm gleich 3-5 Stück. eines für die Jackentasche, eines für die Hemdentasche ect.