Wie effizient die Wurzel von Ganzzahlen berechnen?



  • Der Hintergrund ist, dass ich eine Arithmetik brauch, die auf allen Prozessoren das selbe Ergbnis ergibt.
    Also arbeite ich mit int/long.

    Wie kann ich jetzt möglichst effizient die Wurzel aus x ziehen? In einer for-Schleife so lange alle Werte zu quadrieren, bis die x oder größer rauskommt und dann x-1 zurückzuliefern (bzw. x, sparen wir uns die Einzelheiten), dauert um Welten zu lange.

    Ich hab auch mal versucht, x in ein double zu casten, daraus die Wurzel zu ziehen und von dem (int)Ergebnis-1 angefangen zu zählen, das war schon wesentlich besser. Aber noch immer 8mal langsamer als mittels sqrt von nem double-Wert nur die Wurzel zu ziehen.

    Wie funktioniert sqrt? Lässt sich der Algorithmus auf int/long übertragen?



  • Du kannst eine Wurzelfunktion implementieren die dir x = sqrt(a) liefert, indem du für die Funktion x -> x^2 - a die Nullstelle annäherst (Newton, Mittelwertsatz, ...).



  • Hallo,

    du kannst das Heronverfahren implementieren. Arbeitest mit double oder float
    und castest dann eben auf int. Das Verfahren ist so definiert:

    Xn = 0.5 * (Xn-1 + Eingegebener_Wert/Xn-1)

    Hier ein wenig Code:

    double MySqrt(double a)
    {
       double b = a;
    
          while( !((b*b)>(a-0.001) &&
                  (b*b) <= (a+0.00001)))
             b = 0.5 * (b + a/b);
    
       return b;
    }
    

    Wenn ich jetzt keinen Fehler gemacht hab, sollte es einwandfrei
    funktionieren.

    mfg
    v R



  • Das Problem ist ja das casten. Ich muss in int rechnen, sonst kann es Unterschiede bei verschiedenen Prozessoren geben.
    Sonst würd ich einfach casten und sqrt aufrufen.



  • Optimizer schrieb:

    Das Problem ist ja das casten. Ich muss in int rechnen, sonst kann es Unterschiede bei verschiedenen Prozessoren geben.

    Kannst du das näher erläutern? Ich weiß nicht recht worauf du hinaus willst.



  • double ist auf verschiedenen Prozessoren unterschiedlich und int nicht?

    Das Problem ist hier ja der Nachkommaanteil, der in int ja nicht enthalten
    ist. Vielleicht koenntest du sowas machen:

    struct MyDouble
    {
       int Vorkommaanteil,
           Nachkommaanteil;
    };
    

    Und dann die Funktion anpassen. Nur mal so aus dem Bauch heraus gedacht,
    gibt sicherlich noch bessere Moeglichkeiten.

    mfg
    v R



  • Werd ich mal ins Auge fassen. Was haltet ihr von Fixkomma-Zahlen?
    Ich habe nämlich festgestellt, dass meine Werte für int zu groß werden. Und __int64 scheint saulahm zu sein.



  • Was meinst du mit Fixkommazahlen?

    Angenommen du wuerdest dir so eine Stuktur basteln, waeren denn diese
    32bit Vor- und Nachkommaanteil nicht genug?

    mfg
    v R



  • Ich muss quadrieren. Wenn ich mit fixkomma-zahlen arbeite, wird der Wert dabei nicht so hoch.
    Das Problem mit der Wurzel ist halt, dass ich, egal ob ich jetzt int oder fixpoint nehme, ne Wurzelfunktion brauche, damit ich nicht nach float casten muss.

    Das mit den fixpoint-zahlen habe ich aber schon wieder verworfen. Es steht also die ursprüngliche Frage im Raum 🙂



  • Wie wäre es wenn du dir eine Klasse zum rechnen mit rationalen Zahlen schreibst? Ist nicht so schwer.



  • Ich brauch aber das ganzzahlige (abgerundete, also abgeschnittene) Ergebnis der Quadratwurzel aus einer Ganzzahl.

    ➡ hoffe, das ist jetzt eine ganz korrekte Formulierung 😃



  • Was ich mir alternativ noch vorstellen kann, ist dass du den Nachkommaanteil
    in den Vorkommaanteil rein nimmst. D. h. du musst multiplizieren und rechnest
    dann damit. Zum schluss divisdierst du wieder und da es sich um ein int handelt,
    gehen die Nachkommastellen verloren. D. h. dass du z. B. statt mit 0.5 mit 5
    multiplizierst und spaeter eben durch 10 teilst. Natuerlich muss der Rest
    ebenfalls angepasst werden.

    Ich hab das noch nicht ausprobiert mit o. Code, aber das sollte doch eigentlich
    kein Problem sein. So etwas aehnliches haben wir in unserem Warenwirtschafts-
    programm auf der Arbeit gemacht, da float fuer uns zu wenig Nachkommastellen
    hat und wir aber nicht alles auf double umstellen wollten. also haben wir bei
    den Berechnungen das ganze mal 10.000 genommen und spaeter durch 10.000 geteilt.

    Hoffe du weisst was ich meine.

    mfg
    v R



  • Ok, ich denk mal drüber nach *denk*

    Thx mal an alle.


Log in to reply