Sqrt effizient nur mit Int berechnen

N

Nico1989

Mitglied
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 :D (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
 
Hi

zB.
C: 
    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.
 
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 ?
 
Hi

wie du Zahlen "reinbekommst"?
Du meinst, wie du das aufrufst?
Ganz normal:
C++: 
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 :D
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 :rolleyes:
Jaja, ich muss mehr denken und weniger schreiben...
)
 
Alleeees klar verstehe Danke! :D
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.
 
@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 :D)

@Smartphone, dass keine FP-Zahlen kann: Gibts sowas?
...
 
@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
 
sheel hat gesagt.:
@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 :D)

@Smartphone, dass keine FP-Zahlen kann: Gibts sowas?
...
Zum Vergrößern anklicken....
Der Code von meinen Heron Experimenten wurde aus Wut leider unwiederruflich gelöscht :D 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 :D
 
Zuletzt bearbeitet:
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück