Algorithmus

Benutzeravatar
jan_k
Mausschubser
Mausschubser
Beiträge: 66
Registriert: 7. Jul 2009 15:39
Kontaktdaten:

Algorithmus

Beitrag 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?

test1234
Erstie
Erstie
Beiträge: 13
Registriert: 10. Okt 2009 19:03

Re: Algorithmus

Beitrag von test1234 »

Hast du das Rätsel mittlerweile gelöst?

x muss wohl die Mantisse als Integerzahl sein
Das Ziel moderner Kriegsführung ist die Zerstörung von Produkten menschlicher Arbeitskraft.
Eine hirarchische Gesellschaftsordnung ist nur möglich auf der Grundlage von Armut und Unwissenheit.
Mit anderen Worten heißt das, dass Volk muß immer am Rand der Hungersnot gehalten werden.
Krieg wird immer nur geführt von der herrschenden Klasse gegen die eigenen Untergebenen.
Sein Ziel besteht nicht darin über Eurasien oder Ostasien zu siegen, sondern die Gesellschaftsstruktur zu bewahren.

Benutzeravatar
jan_k
Mausschubser
Mausschubser
Beiträge: 66
Registriert: 7. Jul 2009 15:39
Kontaktdaten:

Re: Algorithmus

Beitrag 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.

Benutzeravatar
Demmi
Kernelcompilierer
Kernelcompilierer
Beiträge: 423
Registriert: 1. Okt 2007 12:56
Wohnort: Darmstadt

Re: Algorithmus

Beitrag 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.
Saying that Java is nice because it works on all Plattforms is like saying that anal sex is nice because it works on all genders.

Nadine
Mausschubser
Mausschubser
Beiträge: 78
Registriert: 4. Okt 2008 14:41
Wohnort: Mainhausen

Re: Algorithmus

Beitrag 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.

test1234
Erstie
Erstie
Beiträge: 13
Registriert: 10. Okt 2009 19:03

Re: Algorithmus

Beitrag 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
Das Ziel moderner Kriegsführung ist die Zerstörung von Produkten menschlicher Arbeitskraft.
Eine hirarchische Gesellschaftsordnung ist nur möglich auf der Grundlage von Armut und Unwissenheit.
Mit anderen Worten heißt das, dass Volk muß immer am Rand der Hungersnot gehalten werden.
Krieg wird immer nur geführt von der herrschenden Klasse gegen die eigenen Untergebenen.
Sein Ziel besteht nicht darin über Eurasien oder Ostasien zu siegen, sondern die Gesellschaftsstruktur zu bewahren.

Nadine
Mausschubser
Mausschubser
Beiträge: 78
Registriert: 4. Okt 2008 14:41
Wohnort: Mainhausen

Re: Algorithmus

Beitrag 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.

Benutzeravatar
jan_k
Mausschubser
Mausschubser
Beiträge: 66
Registriert: 7. Jul 2009 15:39
Kontaktdaten:

Re: Algorithmus

Beitrag 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.

ivoch
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 199
Registriert: 3. Mär 2004 10:51

Re: Algorithmus

Beitrag 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.

mazbu
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 23. Nov 2008 23:44

Re: Algorithmus

Beitrag 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 ...

Daniel Mäurer
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 12. Okt 2009 14:18

Re: Algorithmus

Beitrag 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.

Daniel Mäurer
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 12. Okt 2009 14:18

Re: Algorithmus

Beitrag von Daniel Mäurer »

zur Aufgabenstellung: siehe ivoch's Erklärung.

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: Algorithmus

Beitrag 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?

Benutzeravatar
Demmi
Kernelcompilierer
Kernelcompilierer
Beiträge: 423
Registriert: 1. Okt 2007 12:56
Wohnort: Darmstadt

Re: Algorithmus

Beitrag 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.
Saying that Java is nice because it works on all Plattforms is like saying that anal sex is nice because it works on all genders.

Benutzeravatar
jan_k
Mausschubser
Mausschubser
Beiträge: 66
Registriert: 7. Jul 2009 15:39
Kontaktdaten:

Re: Algorithmus

Beitrag 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.

Antworten

Zurück zu „Archiv“