Was soll ich da zurückgeben?

Metatron

#include "ratNum.h"
#include <math.h>

static long fraction_error = 0L;

/* Sinn und Zweck: sollte den ggT berechnen (Hoffentlich! Da lass ich mich
noch ueberraschen ... */
long gcd(long op1, long op2){
	long temp1 = op1 = abs(op1);
	op2 = abs(op2);
	if(op2 > temp1){
		op1 = op2;
		op2 = temp1;
	}

	if(op1){
		if(op2){
			while(temp1 = op1 - op2){
				if(op2 % temp1){
					op1 = temp1 > op2 ? temp1 : op2;
					if(temp1 < op2)
						op2 = temp1;
				}
				else
					return op2;
			}
			return op2;
		}
		else
			return op1;
	}
	fraction_error |= DIV_ZERO;
	return 1L; 
/* ----->  Hier bin ich ratlos. Wenn der Aufrufer zwei Nullen reinsteckt (z.B.
--- weil ein Bruch gekuerzt werden soll), hat er also anschließend vor, durch
--- den Rueckgabewert zu dividieren. Es ist doch nicht ueblich, dass man es
--- dem Aufrufer zumutet, staendig nachzupruefen, ob irgendwo eine Division
--- durch Null passieren koennte. Kann man das so lassen, dass man also einfach
--- 1 zurueckgibt, auch wenn 1 nicht unbedingt der ggT von zwei Nullen ist.
--- Als Ausweg ist mir nur noch eingefallen, eine globale Variable zu
--- verwenden, die in so einem Fall auf TRUE gesetzt wird, damit sich der
--- Aufrufer letzten Endes auch vergewissern kann, dass waehrend des Rechnens
--- kein Fehler aufgetreten ist. Stichwort: Fehlerbehandlung, wenn man nicht
--- vorhersehen kann, welche Parameter in die Funktion reingesteckt werden.
--- Wie wuerdet Ihr dem Problem vorbeugen ?
--- Bin dankbar fuer jeden Tipp.*/
}

Herauskommen sollte letzten Endes eine Art Mini-Lib, mit der man so halbwegs in Q rechnen kann.
mfg

Nexus

Versuch es doch mit Exception-Handling. Alternativ könntest du auch je nach Fehler negative Werte zurückgeben lassen.

camper

Im Kontext des Kürzen von Brüchens kann der Fall, dass beide Operanden 0 sind, eigentlich gar nicht auftreten (dann wäre der Bruch vorher schon undefiniert) - insofern dürfte eine Fehlerbehandlung an dieser Stelle nicht zwingend erforderlich sein. Abgesehen davon liefert die übliche rekursive Form des euklidische Algorithmus

long ggt(long a, long b) {
    return b != 0 ? ggt( b, a % b ) : a;
}

hier bereits das brauchbare Ergebnis 0. Da es von vornherein ein Fehler des Aufrufers ist, kann er sich auch mit diesem Ergebnis auseinandersetzen. Die Fälle, wenn nur ein Argument 0 ist, benötigen dagegen ohnehin keine Sonderbehandlung.

Metatron

int smaller(const Fraction* op1, const Fraction* op2){
 /*
 if(op1->num > 65000 && op2->den > 65000 ||
    op1->num < -65000 && op2->den > 65000)
   fraction_error |= OVERFLOW;
 */

 return op1 && op2 ?
 op1->num*op2->den < op2->num*op1->den :
 0;
}

Ein ähnliches Problem ist jetzt hier eingetreten, wo der erste Operand darauf überprüft werden soll, ob er kleiner als der zweite ist.
Und zwar ist sehr schwer vorherzusehen, ob z.B. möglicherweise
op1->num * op2->den den zulässigen Wertebereich für long über- oder unterschreitet, und als Folge davon ein falsches Ergebnis zurückgeliefert wird.

Das, was ich jetzt erstmal auskommentiert habe, deckt immer noch nicht alle Fälle ab, in denen ein zu großer oder zu kleiner Wert für den Datentyp long herauskommen könnte, weil z.B. auch wenn nicht beide Bedingungen erfüllt sind, also z.B. 100000 mal 30000 gerechnet werden müsste, könnte trotzdem noch ein Overflow passieren. Es ist ja gar nicht abzuschätzen, in wie vielen Fällen das passieren könnte. Gibt es eine Möglichkeit, einfach die Multiplikation auszuführen,, und dann erst herauszufinden, ob ein Overflow passiert ist. Angeblich soll das ja in irgendeinem Prozessor-Register abgespeichert werden, wenn ein Overflow passiert, aber wie kann ich das abfragen (soferne es denn überhaupt möglich ist, von einer Hochsprache wie C++ aus?)?

Besten Dank für Tipps !

camper

Metatron schrieb:

Gibt es eine Möglichkeit, einfach die Multiplikation auszuführen,, und dann erst herauszufinden, ob ein Overflow passiert ist.

Kurz gesagt: nein. Überlaufe vorzeichenbehafteter Integeroperationen sind praktisch immer undefiniert. Selbst wenn dem nicht so wäre, könnte man mit dem Ergebnis nicht viel anfangen: denn dass das Ergebnis falsch ist, erkennt man direkt ja nur, wenn man es z.B. durch einen Faktor teilt und dann mit dem anderen vergleicht. Dann hätte man aber von vornherein testen können, ob ein Überlauf auftreten wird.

bool has_exact_product(int a, int b){ // true, wenn a*b als int darstellbar ist
  return a == 0
      || std::numeric_limits<int>::max() / abs( a ) <= abs( b )
// Spezialfall bei 2er-Komplementdarstellung, hier ist -max() != min()
// und min() eine 2er-Potenz, mithin müssten beide Faktoren für dieses Ergebnis 2er-Potenzen sein
      || ( abs( a ) & abs( a ) - 1 ) == 0 && std::numeric_limits<int>::min() / a == b;
}

Edit: der Fall, dass a oder b jeweils std::numeric_limits<int>::min() sind, muss bei 2er-Komplement ebenfalls gesondert behandelt werden, abs ist dann undefiniert...

Natürlich kann es möglich sein, so etwas durch direkte Implementierung in Assembler zu vereinfachen und zu beschleunigen. Das sollte im Interesse der Übersichtlichkeit aber nur eine optionale Optimierung sein.

Metatron

Danke für die erneute Hilfe. Ich war überrascht, dass sich Euklid's ggT-Algo in einer einzigen Codezeile notieren lässt.
thx mfg

camper

Metatron schrieb:

Danke für die erneute Hilfe. Ich war überrascht, dass sich Euklid's ggT-Algo in einer einzigen Codezeile notieren lässt.
thx mfg

In dieser Form kommt er ggf. nicht mit negativen Zahlen zurecht, je nachdem, wie sich das jeweilige System bei Divisionen mit negativen Zahlen verhält. Aber das kann man ja leicht durch einen entsprechenden Aufruf ausgleichen.

Generell würde ich für derartige Probleme interne Rechnungen immer mit vorzeichenlosen Zahlen durchführen - man erspart sich so einige Spezialfälle und hat mehr Möglichkeiten, mit Überläufen umzugehen.