Seite 1 von 2

Algorithmus

Verfasst: 20. Nov 2009 22:26
von jan_k
Hallo,

ich versuche gerade den Algorithmus für die Wurzeln von Gleitkommazahlen nachzuvollziehen.

Angenommen ich will die Wurzel der Zahl 9 ausrechnen.

1.Schritt

\(\sqrt{X} = \sqrt{Mantisse * 2^{2e}} = \sqrt{Mantisse} * 2^e\)

Vereinfacht sei die Darstellung von 9 als Gleitkommazahl folgende: \(1,001_{(2)} * 2^3\)

Da der Exponent ungerade ist, muss ich ihn um eins verringern und die Mantisse verdoppeln. Das ergibt:

\(10,01_{(2)} * 2^2\)

Jetzt kann ich in die Formel einsetzen und erhalte:

\(\sqrt{10,01_{(2)}} * 2^1\)

2. Schritt

Da ich die Mantisse als Integerzahl brauche muss ich sie zwei mal linksshiften, also mit \(2^2\) (s ist also 2) multiplizieren.

Soweit so gut, jetzt kommt allerdings eine seltsame Formel:

\(2^s * y = 2^s * \sqrt{x}\)

Ich gehe mal davon aus, dass y hier die Mantisse ist, aber was ist dann x? Wird in dem Schritt die Mantisse ersetzt mit der Wurzel der Ausgangszahl, also in meinem Beispiel 9? Das würde ja wenig Sinn ergeben da \(Mantisse \not= \sqrt{9}\).

Kann mir jemand auf die Sprünge helfen?

Re: Algorithmus

Verfasst: 21. Nov 2009 14:29
von test1234
Hast du das Rätsel mittlerweile gelöst?

x muss wohl die Mantisse als Integerzahl sein

Re: Algorithmus

Verfasst: 21. Nov 2009 16:00
von jan_k
test1234 hat geschrieben:Hast du das Rätsel mittlerweile gelöst?
Leider nicht
test1234 hat geschrieben:x muss wohl die Mantisse als Integerzahl sein
Die Mantisse als Integerzahl ist \(y * 2^s\). Ich bin mittlerweile der Meinung dass hier einfach Schrittweise die Wurzel gezogen wird, x also \(y^2\) ist.

Ganz sicher bin ich mir aber noch nicht.

Re: Algorithmus

Verfasst: 21. Nov 2009 21:08
von Demmi
Disclaimer: Ich muss das Praktikum nicht machen, weil ich GdI3 schon letztes Jahr gemacht hab. Folglich hab ich auch keine Ahnung, ob das was ich hier schreibe 100%ig den Anforderungen entspricht. Aber ich denke so ungefähr sollte es passen ;)

Ich glaube ich das hab halbwegs verstanden, wie die Aufgabenstellung gemeint ist:
Problem: Wir können nur Wurzeln aus Ganzzahlen ziehen.
Lösung: Wir betrachten Mantisse und Exponent einer FP-Zahl getrennt. Den Exponenten halbieren wir, aus der Mantisse ziehen wir die Wurzel. (Sonderfall Exponent ist ungerade: siehe Aufgabenstellung)

Hier mal ein Beispiel (Nur Single-Precision, aber sicher analog anwendbar auf Doubles):
23,125 = 0 1000 0011 01110010000000000000000
VZ=0=+
Exponent = 4
Mantisse = 1,4453125 (dez) = 1,0111001 (bin)

Jetzt Exponenten prüfen, der ist 4 und damit gerade, wunderbar wir müssen schonmal nicht verdoppeln.
Nachkommastellen (binär!) = 7 = s.

So und jetzt denken wir kurz nach. Wir wollen die Wurzel der Mantisse ziehen, können aber nur aus Ganzzahlen Wurzeln ziehen. Also shiften wir unsere Mantisse erstmal um s=7 nach links bzw. multiplizieren mit 2^7
=> 1011 1001 (bin) = 185 (dez)
Wenn wir da jetzt die Wurzel ziehen würden müssten wir anschließend wieder durch 2^(s/2) dividieren um die Wurzel aus der Mantisse zu erhalten. Unschön, weil (in unserem Fall) 2^3,5 nicht ganzzahlig ist. Also tricksen wir etwas: Wir shiften um 2s = 14 bzw. multiplizieren mit 2^14 und ziehen dann erst die Wurzel.
=> 1,4453125*2^14 = 23680(dez)
Dann müssen wir noch durch 2^s teilen, in unserem Fall also 2^7.
Dieses Ergebnis wird dann noch mit 2^(Exp/2) multipliziert und fertig ist die Wurzel. Nicht schön, aber sollte funktionieren.

\(\sqrt{23,125}=4,80884602=2^{Exp/2}*\sqrt{2^{2s}*Mantisse}/2^s =(2^2*\sqrt{2^{14}*1,4453125})/2^7=(2^2*\sqrt{23680})/2^7\)

Jetzt müsste man nur noch um diese blöde Division rumkommen. Aber darüber hab ich mir jetzt noch keine großen Gedanken gemacht. Sollte irgendwo was nicht richtig sein, sagt bescheid.

Re: Algorithmus

Verfasst: 22. Nov 2009 17:22
von Nadine
anscheinend weiß niemand so genau, was eigentlich genau implementiert werden soll, zumindest die x personen, welche ich fragte.

unter Aufgabenstellung steht, dass man die beiden vorgestellten verfahren implementieren soll.
das erste ist dann wohl das heron-verfahren, welches keinerlei probleme darstellt.
das zweite, nehme ich an, ist wurzeln von gleitkommazahlen, welches sich durch erweiterung von wurzelberechnung von ganzzahlen implementieren lässt.

auf seite 1 des aufgabenblatts steht eine summenformel, welche ich bereits implementierte. jetzt stellte sich die frage, wie ich weiter verfahre. auf seite 2 erscheinen dann gleich 2 vielleicht wichtige formeln (2. & 3.). wenn ich diese aber genauer studiere, merke ich, dass ich meine bereits implementierte summenformel wohl gar nicht brauche?

welche formeln soll ich nun implementieren und verknüpfen?
mir ist zur zeit alles unklar und jeder spekuliert was anderes.
da ich aufgrund von übungen und vorlesungen zu keiner der 3 wöchentlichen sprechstunden erscheinen kann, erwarte ich hier eine antwort.
vielen dank.

Re: Algorithmus

Verfasst: 22. Nov 2009 20:39
von test1234
mir wird das jetzt alles zu blöd, ich hämmer das was ich denke !heute! nacht in die maschine. und dann ist das !heute! vorbei.

das dauert mir nämlich schon viel zu lange

Re: Algorithmus

Verfasst: 22. Nov 2009 21:02
von Nadine
und dann fliegt man auch noch fast durch's testat, weil nicht klar geäußert wurde, was man machen soll, trotzdem im forum stand, dass man bestehen sollte, wenn man die und die abfrage nicht hat.

traurig.

Re: Algorithmus

Verfasst: 22. Nov 2009 22:29
von jan_k
Nadine hat geschrieben:und dann fliegt man auch noch fast durch's testat, weil nicht klar geäußert wurde, was man machen soll, trotzdem im forum stand, dass man bestehen sollte, wenn man die und die abfrage nicht hat.

traurig.
Nächstes Mal bei jemand anderem testieren. Auch wenns jetzt im Nachhinein nichts mehr bringt, aber unser Tutor war beim Korrektheitscheck der römischen Zahlen ziemlich locker, weils eben nicht klar definiert wurde.

Danke an Demmi für das Beispiel.

Re: Algorithmus

Verfasst: 22. Nov 2009 23:33
von ivoch
Nadine hat geschrieben:anscheinend weiß niemand so genau, was eigentlich genau implementiert werden soll, zumindest die x personen, welche ich fragte.
Zu implementieren sind:

1. Das Heron-Verfahren - yi+1 = 1/2 * (yi + x/yi) <- hier könnt ihr zwar eine beliebige Zahl für y0 wählen, aber die Anzahl der Iterationen, die notwendig sind, hängen von dieser Zahl ab. Als Beispiel: bei x = 16 und y0 = 8, haben wir für y1 = 5, was nicht nah genug an den eigentlichen Wert von der Wurzel von x (=4) ist. Die nächste Iteration gibt uns aber schon y2 = 4,1 - und das ist schon mal viel besser. y3 = 4,001 usw.

Wenn wir 500 als Startwert gewählt hätten, würden die Ergebnisse der Iterationen so aussehen: y1 = 250,016; y2 = 125,04; y3 = 62,58 usw - hier würden wir schon viel mehr Iterationen brauchen, um nah genug an 4 ranzukommen.

Ein Teil eurer Aufgabe ist es, sich zu überlegen, welche Zahl am besten geeignet für den Startwert ist (Tipp: gibt es eine "beste" Zahl, die für alle x die kleinstmögliche Anzahl von Iterationen braucht?)


2. Das Binary-Search-Verfahren (binäre Suche) - y = Σ(2^i * bi) mit i = 0 bis n. Diese Formel eignet sich aber nur für ganze Zahlen, deswegen müsst ihr eure Gleitkommazahlen mit den gegebenen Formeln umwandeln.

Re: Algorithmus

Verfasst: 23. Nov 2009 13:56
von mazbu
aber ich habe eine Frage, wie kann ich Mantise nehmen ?? Zuerst denke ich mit Bit Operation aber Bit Operation gülstig nur mit 32bit aber in dieser Aufgabe muss man double benutzten und double ist 64 bit ... ich denke wenn ich Mantise habe , kann ich Wurzel machen ...

Re: Algorithmus

Verfasst: 23. Nov 2009 14:05
von Daniel Mäurer
Nadine hat geschrieben:und dann fliegt man auch noch fast durch's testat, weil nicht klar geäußert wurde, was man machen soll, trotzdem im forum stand, dass man bestehen sollte, wenn man die und die abfrage nicht hat.

traurig.
Wer deswegen durchs testat geflogen ist kann sich gerne bei mir melden.

Re: Algorithmus

Verfasst: 23. Nov 2009 14:14
von Daniel Mäurer
zur Aufgabenstellung: siehe ivoch's Erklärung.

Re: Algorithmus

Verfasst: 23. Nov 2009 16:10
von s!mon
Ich frag jetzt kurz nochmal nach. Nach Daniels Erklärung müsste ich bei doppelter Genauigkeit zunächst meine Zahl um 104 Shiften (weil wir 52 Nachkommastellen haben), dann die Wurzel ziehen und dann halt noch mit 2^(Exp/2) multiplizieren. Ist das richtig so?! Klingt seltsam für mich :P

Also sozusagen betrachte ziehe ich die Wurzel aus meiner Mantisse und setze das Ergebnis dann wieder hinters Komma (und nicht an die 26te Stelle danach oder so)

Brauche ich das versteckte Bit der Mantisse?

Re: Algorithmus

Verfasst: 23. Nov 2009 17:02
von Demmi
s!mon hat geschrieben:Ich frag jetzt kurz nochmal nach. Nach Daniels Erklärung müsste ich bei doppelter Genauigkeit zunächst meine Zahl um 104 Shiften (weil wir 52 Nachkommastellen haben)
Dein s geht nur bis zur letzten 1 nach dem Komma - also im schlimmsten Fall 52, richtig. Aber du musst schauen, dass du nicht deinen Integer-Bereich überschreitest. Keine Ahnung wie genau da jetzt die Grenzen sind, aber ich vermute mal, dass du alles über 32-er Shifts (also s>16) vergessen kannst, weil das eh nicht mehr in nen standard Int reinpasst. Und genau den brauchst du ja für dein 2. Verfahren. Ohne Gewähr!
s!mon hat geschrieben:Brauche ich das versteckte Bit der Mantisse?
Ja, siehe mein Beispiel.

Re: Algorithmus

Verfasst: 23. Nov 2009 19:12
von jan_k
Demmi hat geschrieben:aber ich vermute mal, dass du alles über 32-er Shifts (also s>16) vergessen kannst, weil das eh nicht mehr in nen standard Int reinpasst.
Meiner Meinung nach sogar nur ein Maximum von s = 14, da man evtl die Mantisse anpassen muss wegen ungeradem Exponent (verdoppeln) und in ein Int-Register nur ein Wert von maximal \(2^{31}\) reinpasst.

Ich werds auf jeden Fall erstmal so implementieren und hoffen, dass die Genauigkeit ausreicht.