Ungefähres Wurzelziehen ohne Kommazahlen?

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.