Sqrt effizient nur mit Int berechnen

[Nico1989]

Hi!
Wie es der Titel schon verrät suche ich nach einem Verfahren zur Wurzelberechnung ohne verwendung von Fließkommazahlen, ich möchte also nur Integer verwenden.

Wie schon in meinen ersten Threads erwähnt mache ich gerade meine Anfänge in der Programmierwelt (nur so als anmerkung)

Mein erster Gedanke war das Heron verfahren also im Prinzip eine Form der Händischen Wurzelberechnung in Code verwandeln doch dabei ist nicht wirklich was rausgekommen.

Ich bin für jeden Ansatz / für jede Hilfe dankbar!

Mfg

Nico

 

[sheel]

Hi

zB.

    unsigned int sqrt32(unsigned long n)  
    {  
        unsigned int c = 0x8000;  
        unsigned int g = 0x8000;  
      
        for(;;) {  
            if(g*g > n)  
                g ^= c;  
            c >>= 1;  
            if(c == 0)  
                return g;  
            g |= c;  
        }  
    }

geklaut von hier, Vierter in C:
http://www.codecodex.com/wiki/Calculate_an_integer_square_root

Nicht ausprobiert, soll aber schnell sein.
Mal vergleichen...

edit: Hm ok, das ist Mist (?)
Deutlich mehr Zeitverbrauch als die double-Variante sqrt.

 

[Nico1989]

Danke für die schnelle Antwort, auch wenn es nicht der schnellst mögliche ist würde ich ihn gern verstehen falls du die Zeit dafür noch übrig hast.
Wie bekomme ich da Zahlen rein ? und 0x8000 steht doch in Verbindung mit Register Addressen oder täusch ich mich da ?

 

[sheel]

Hi

wie du Zahlen "reinbekommst"?
Du meinst, wie du das aufrufst?
Ganz normal:

int i = sqrt32(100);
//i ist 10

Aber, wie geschrieben, die Standardfunktion sqrt ist (bei mir zumindest) viel schneller
Also sqrt statt sqrt32, und den Code oben gar nicht verwenden.

Und nein, im Code kommt nichts mit Speicheradressen vor.
Das 0x8000 ist die Zahl 32768 einfach anders aufgeschrieben.
(Warum das da gemacht wird? Keine Ahnung
Hab nicht überlegt, warum das funktioniert.

Bei genauerer Überlegung bin ich grade draufgekommen,
dass kein C-Code-Workaround der Welt
schneller als eine spezielle Asm-Op sein sollte
Jaja, ich muss mehr denken und weniger schreiben...
)

 

[Nico1989]

Alleeees klar verstehe Danke!
Das die Standardfunktion schneller ist ist in dem Fall nicht so schlimm es ging bei meiner Aufgabenstellung lediglich darum, dass man keine Fließkommazahlen verwenden darf. Da es theoretisch auf einem Smarthphone ohne Coprozessor für Fließkomma arithmetik laufen sollte.

 

[sheel]

@Aufgabenstellung:
Dann ist es vielleicht nicht so ideal, wenn wir den Code nicht nachvollziehen können
Du hast ja selbst auch was versucht, was ist denn dabei rausgekommen?
(Mal wieder schlau machen, wie die händische Wurzelberechnung ging...schon so lang her )

@Smartphone, dass keine FP-Zahlen kann: Gibts sowas?
...

 

[cwriter]

@sheel
Nein, das gibt's nicht. Aber vergleichsweise langsame Emulationen von ARM-Prozessoren.

Back to topic: Das Ziel ist schon eigener Algorithmus, oder? Denn auch auf ARM-Prozessoren dürfte die Standardvariante schneller sein, wenn auch mit Casts.

Gruss
cwriter

 

[Nico1989]

@Aufgabenstellung:
Dann ist es vielleicht nicht so ideal, wenn wir den Code nicht nachvollziehen können
Du hast ja selbst auch was versucht, was ist denn dabei rausgekommen?
(Mal wieder schlau machen, wie die händische Wurzelberechnung ging...schon so lang her )

@Smartphone, dass keine FP-Zahlen kann: Gibts sowas?
...

Der Code von meinen Heron Experimenten wurde aus Wut leider unwiederruflich gelöscht ich probier grad noch bissle rum mit dem Newton Verfahren ma sehn was dabei rauskommt.

@cwriter
Ja im Prinzip gehts in diesem Übungsbeispiel um das verfassen eines eigenen Algos, bzw. um das auseinandersetzen mit den verschiedenen Laufzeitkomplexitäten der bekannten Wurzelberechnungen...und wie ich mitlerweile mitbekommen hab gibts da wirklich ziemlich krasse unterschiede

 

[sheel]

Newton/Heron: Selbes Prinzip, und beide sind Kommazahlen-lastig.
Das: http://de.wikipedia.org/wiki/Schriftliches_Wurzelziehen schaut nach ints aus

 

[Nico1989]

Jop das werd ich auch noch probiern, ich versuch mich jetzt noch daran