Umformung eines Algorithmus um Überlauf zu verhindern

24.10.2011, 11:01

Azzie2k8

Umformung eines Algorithmus um Überlauf zu verhindern

Gegen ist die Gleichung $\begin{eqnarray*} r = \sqrt{x² + y²} \end{eqnarray*}$

Die Zahl r liegt im darstellbaren Bereich. x² und y² verursachen, allerdings bei der Berechnung einen Überlauf (sind zu groß für den gegebenen Speicher).

Nun soll ich jeweils für die Fälle $\begin{eqnarray*} |x| \leq |y| \end{eqnarray*}$ und $\begin{eqnarray*} |x| > |y| \end{eqnarray*}$ ein Lösung durch Umformung des Algorithmus finden.

Für den Fall das y größer gleich x ist hatte ich bereits Überlegungen angestellt und bin durch Umformung auf folgendes gekommen $\begin{eqnarray*} \frac{r²}{y} = \frac{x²}{y} + y \end{eqnarray*}$

Jetzt stelle ich mir die Frage, bin ich da überhaupt auf dem richtigen Weg ? Vor allem stellt meine Lösung doch nur eine Lösung für x<y (wenn überhaupt) dar oder ? Was ist wenn x = y ?

Ich hoffe mich kann jemand erleuchten Big Laugh

24.10.2011, 13:04

Steffen Bühler

Auf diesen Beitrag antworten »

RE: Umformung eines Algorithmus um Überlauf zu verhindern
Dein Ansatz ist schon richtig. Du kannst das zum Beispiel prüfen, indem Du y=1000 und x=1 setzt. Mit 16-Bit-Zahlen würde die übliche Formel Probleme machen, Deine erstmal nicht: auf der rechten Seite steht jetzt 1000,001.

Jetzt mußt Du Dir überlegen, wie's weitergeht. Beide Seiten mal y verbietet sich aus genannten Gründen. Also: wie kommst Du jetzt auf r?

Viele Grüße
Steffen

24.10.2011, 13:58

Azzie2k8

Auf diesen Beitrag antworten »

Danke für deine Antwort.

Ich muss zu meiner Schmach gestehen, dass ich auch schon mal besser Mathe konnte Big Laugh

Also, ich könnte nun erstmal hingehen und so umformen

$\begin{eqnarray*} r^2 * \frac{1}{y} = \frac{x^2}{y} + y \end{eqnarray*}$

Wurzel ziehen (ist die linke seite richtig ?)

$\begin{eqnarray*} \sqrt{r^2 * \frac{1}{y}} = \sqrt{\frac{x^2}{y} + y} \end{eqnarray*}$

Umschreiben

$\begin{eqnarray*} r * \sqrt{\frac{1}{y}} = \sqrt{\frac{x^2}{y} + y} \end{eqnarray*}$

Durch Wurzel(1/y) teilen und umformen

$\begin{eqnarray*} r = \sqrt{(\frac{x^2}{y} + y) * \frac{1}{y} } \end{eqnarray*}$

Dies sollte zumindest für den Fall das y größer als x ist helfen. Ich bin mir aber bei den letzten 2 Umformungen nicht sicher ob ich das so machen darf... Aber was ist mit dem Fall das x = y ist ? Das ist doch dann eigentlich nicht möglich. Sollte x > y sein, kann ich das bisherige ja einfach umkehren.

24.10.2011, 14:41

Steffen Bühler

Auf diesen Beitrag antworten »

Zitat:

Original von Azzie2k8
$\begin{eqnarray*} r * \sqrt{\frac{1}{y}} = \sqrt{\frac{x^2}{y} + y} \end{eqnarray*}$

Bis hierher alles klar.

Zitat:

Durch Wurzel(1/y) teilen und umformen

$\begin{eqnarray*} r = \sqrt{(\frac{x^2}{y} + y) * \frac{1}{y} } \end{eqnarray*}$

Hoppla. Sollte wohl

$\begin{eqnarray*} r = \sqrt{(\frac{x^2}{y} + y) \cdot y } \end{eqnarray*}$

heißen, oder?

Dann wäre aber schon wieder eine Multiplikation mit Überlauf fällig, wenn y=1000 ist. Das Unter-die-Wurzel-Ziehen war also nicht zielführend. Aber es muß ja auch nicht sein...

Zitat:

Aber was ist mit dem Fall das x = y ist ? Das ist doch dann eigentlich nicht möglich.

Dein Ansatz funktioniert in der Tat nur, solange das Quadrieren der kleineren Zahl noch keinen Überlauf verursacht. Sind mehr sich x und y nähern, desto eher gibt es Probleme. Vielleicht findet sich ja noch eine verbesserte Variante. Ich hätte da so eine Idee...

Zitat:

Sollte x > y sein, kann ich das bisherige ja einfach umkehren.

So ist es.

Viele Grüße
Steffen

24.10.2011, 15:11

Azzie2k8

Auf diesen Beitrag antworten »

Nett dass du da solche Ideen hast Big Laugh

trotzdem muss ich nochmal hier öffentlich nachdenken Big Laugh

Du hastz beim letzten Umformungsschritt tatsächlich meinen Fehler entdeckt, ich sagte ja meine Mathekenntnisse waren mal besser....

Aber ich muss sagen, ich glaube ich geb auf. Ich hab nun wirklich schon einige Blätter mit nem haufen unsinniger Umformungen vor mir liegen, sehe aber keine Lösung. Der Ansatz aus dem ersten Post wird wohl mein Schlussergebnis sein...

Nur um nochmal was zusammen zu fassen.

letzter Schritt ist also momentan
$\begin{eqnarray*} r = \sqrt{\frac{x^2}{y}+ y} * \sqrt{y} \end{eqnarray*}$

Das sollte doch zumindest eine Teillösung sein und eine weiter Lösung für x sollte doch auch schonmal was Wert sein. Oder sehe ich das gerade falsch ? Es sollte, kein Überlauf entstehen, da y nicht quadriert wird ?

24.10.2011, 15:13

René Gruber

Auf diesen Beitrag antworten »

Ich weiß überhaupt nicht, wie man hier zu der Fragestellung etwas vernünftiges sagen kann, solange man nichts genaueres weiß über das zugrunde liegende Datenformat (Integer? Fließ- oder Festkomma?). verwirrt

24.10.2011, 15:18

Azzie2k8

Auf diesen Beitrag antworten »

Danke für deinen post René. Allerdings bietet die Aufgabenstellung keine weiteren Informationen.

Gegeben ist die Gleichung aus dem ersten Post und diese Aufgabe:

"In der Formel kann für große x,y (reelle Zahlen) Exponentenüberlauf auftreten, obwohl r im darstellbaren Bereich läge. Finden Sie durch Umformung eine Darstellung der obigen Formel, die Exponentenüberlauf verhindert.

Hinweis: betrachten sie die Fälle x <= y, x > y "

Wie du siehst kann ich aus der Aufgabenstellung lediglich schließen, dass eine Quadrierung der größeren Zahl vermieden werden soll. Angaben zur Bit-Zahl oder Mantissenlänge sind nirgendwo gegeben.

24.10.2011, 15:20

Steffen Bühler

Auf diesen Beitrag antworten »

Zitat:

Original von Azzie2k8
$\begin{eqnarray*} r = \sqrt{\frac{x^2}{y}+ y} * \sqrt{y} \end{eqnarray*}$

Das sollte doch zumindest eine Teillösung sein und eine weiter Lösung für x sollte doch auch schonmal was Wert sein.

Ich finde auch. Mein Ansatz wäre übrigens $\begin{eqnarray*} \frac {r^2}{x \cdot y} \end{eqnarray*}$ gewesen, aber da braucht man gar keine Fallunterscheidung mehr, daher hatte ich das nicht weiter verfolgt.

Viele Grüße
Steffen

24.10.2011, 15:21

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Azzie2k8
"In der Formel kann für große x,y (reelle Zahlen) Exponentenüberlauf auftreten, obwohl r im darstellbaren Bereich läge.

Das ist doch schon mal die gesuchte Info: Also Fließkomma, aber der Exponentenbereich ist nicht ausreichend für das Problem hier!

(Wieder mal so ein Beispiel der Vorenthaltung wichtiger Informationen im Ausgangsposting.)

Die natürliche Vorgehensweise wäre m.E. die folgende, ich gehe dabei von binärem Fließkomma aus:

Sei $\begin{eqnarray*} n \end{eqnarray*}$ der Binärexponent der betragsmäßig größeren der beiden Fließkommazahlen $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} y \end{eqnarray*}$ . Dann berechnet man einfach

$\begin{eqnarray*} x' = \frac{x}{2^n}, \quad y' = \frac{y}{2^n} \end{eqnarray*}$ .

(entspricht bei binärem Fließkomma einer einfachen Subtraktion des Wertes $\begin{eqnarray*} n \end{eqnarray*}$ vom Exponenten), dann rechnet man

$\begin{eqnarray*} z' = \sqrt{x'^2+y'^2} \end{eqnarray*}$ sowie $\begin{eqnarray*} z = 2^nz' \end{eqnarray*}$

(letzteres entspricht dann einer einfachen Addition des Wertes $\begin{eqnarray*} n \end{eqnarray*}$ zum Exponenten von $\begin{eqnarray*} z' \end{eqnarray*}$ ), fertig.

24.10.2011, 16:43

Azzie2k8

Auf diesen Beitrag antworten »

Entschuldige, ich war in meiner Dummheit überzeugt, dort keine weitere Information zu sehen. Du hast mich nun eines anderen belehrt.

Verstehe ich dich richtig, dass du hier von Binärzahlen ausgehst ? Diese Information kann ich aus der Aufgabenstellung nicht erkennen.

das $\begin{eqnarray*} 2^{n} \end{eqnarray*}$ bezieht sich in dem Fall doch sicherlich auf die Basis des gesamten Zahlensystems ? Von daher kann ich mir doch nicht sicher sein, ob die 2 dort stehen darf ?

Was du im Grund getan hast ist eine raffinierte Verschiebung des Quadrierens ?

Vielen Dank für den genialen Ansatz, wie gesagt nur mit der 2 als Basis bin ich mir nicht so sicher...

24.10.2011, 16:51

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Azzie2k8
wie gesagt nur mit der 2 als Basis bin ich mir nicht so sicher...

Naja, man kann das ganze genausogut mit Basis 10 machen, nur ist die in "realer" Hard- oder Software eher selten als internes Zahlenformat anzutreffen. Augenzwinkern

24.10.2011, 18:22

Azzie2k8

Auf diesen Beitrag antworten »

okay aber wenn x und y element der menge der reellen zahlen sind kann ich dann nicht davon ausgehen dass ich die basis 10 habe? Denn nicht alle reellen zahlen sind im 2er system darstellbar, oder?

24.10.2011, 19:10

sootnstars

Auf diesen Beitrag antworten »

Theoretisch schon, praktisch hast du aber in der Fließkommazahl (shcau mal auf wikipedia) immer ungenauigkeiten drin. Diese Datentypen sind aber nunmal für Basis 2 spezifiziert und auf dem Papier tritt kaum ein Überlauf auf.. Augenzwinkern

Neue Frage »

Antworten »

Umformung eines Algorithmus um Überlauf zu verhindern

Verwandte Themen