3. [Gelöst] Overflow Test - Integers

[Gelöst] Overflow Test - Integers


  • Hallo zusammen,

    angenommen ich möchte überprüfen, ob das Addieren von zwei Integern a und b einen overflow erzeugen wird, welche (der beiden) Methode(n) ist besser/sind am besten?

    const int maxint = std::numeric_limits<int>::max();
const int minint = std::numeric_limits<int>::min();

bool add_is_safe(int lhs, int rhs)
{
    if (lhs > 0 && rhs > 0)
        return (lhs <= maxint - rhs);
    else if (lhs < 0 && rhs < 0)
        return (lhs >= minint + rhs);
    else
        return true;
}
// oder (von StackOverflow)
// ACHTUNG: Das hier ist falsch
std::size_t log(int n)
        // highest position of 1 bit
{
    std::size_t bits{ 0 };
    while (n) {
        ++bits;
        n >>= 1;
    }
    return bits;
}
bool add_is_safe(int lhs, int rhs)
{
    std::size_t lhsbits = log(lhs);
    std::size_t rhsbits = log(rhs);
    std::size_t total = sizeof(int) * 8;
    return (lhsbits < total && rhsbits < total);
}

    Das Prinzip würde ich dementsprechend auch auf die anderen Operatoren übertragen...

    LG

    0
  • N

    Wieso meinst du das zu brauchen?

    0

  • Ich habe eine Klasse, die ca. so aussieht

    class Rational {
//...
private:
    int num;
    int denom;
};

    Und da gibt es + - * /.
    Ich will eine exception werfen, wenn eine dieser Operationen ein falsches Ergebnis ergeben würde (aufgrund dessen, dass das Ergebis nicht in einen int passt.

    0

  • Die zweite Version ist falsch.

    0

  • mgaeckler schrieb:

    Die zweite Version ist falsch.

    Willst du mir auch erklären warum? Hab das von hier:
    http://stackoverflow.com/questions/199333/best-way-to-detect-integer-overflow-in-c-c

    0
  • N

    HarteWare schrieb:

    Ich will eine exception werfen, wenn eine dieser Operationen ein falsches Ergebnis ergeben würde (aufgrund dessen, dass das Ergebis nicht in einen int passt.

    Selbe Frage. Signed overflow ist UB. Lass es einfach UB bleiben Bei normalen Integern oder std::complex passiert das ja auch nicht.

    0

  • Ich hätt' gerne integers die werfen, wenn sie was nicht können ...

    0

  • HarteWare schrieb:

    mgaeckler schrieb:

    Die zweite Version ist falsch.

    Willst du mir auch erklären warum? Hab das von hier:
    http://stackoverflow.com/questions/199333/best-way-to-detect-integer-overflow-in-c-c

    log terminiert nicht, wenn es mit einer negativen Zahl aufgerufen wird.

    Für positive Werte liefert addissafe immer True. Das ist Unfug.

    0

  • D.h., angenommen ich rechne jetzt zwei dieser Brüche zusammen, dann überlasse ich es dem Anwender zu kapieren, dass das Ergebnis Schwachsinn ist, weil er eben Zahlen so gewählt hat, dass die Brüche zu groß wurden?

    Vielleicht habe ich

    Überläufe werden nicht vernünftig behandelt; nicht einmal dann, wenn das (normalisierte) Ergebnis exakt darstellbar ist.

    auch einfach nur falsch verstanden, ich mein ist ja nett und gut und alles, dass die Leute mir Tips geben was ich ja auch will, aber da ist so wenig Info dabei, dass ich auch nicht so recht weiß, wo ich das ansetzten soll. Wenn ich so schlau wäre, dass mir das alles gleich klar ist, bräuchte ich die Hilfe ja auch nicht...

    Für die Leute, die jetzt hier verwirrt sind, ich habe ein bisschen Code im Projekte Forum gepostet und hab auf Anfrage ein paar Verbesserungsvorschläge erhalten 👍 . Ich hab einige schon, so gut ich konnte, umgesetzt, aber bei manchen bin ich mir bei deren Umsetzung unsicher, deshalb z.B. dieser Thread (soll keine Selbstpromotion sein)

    @mgaeckler
    verstehe, jetzt ist es mir klar, danke.

    0
  • C
    Mod

    HarteWare schrieb:

    Vielleicht habe ich

    Überläufe werden nicht vernünftig behandelt; nicht einmal dann, wenn das (normalisierte) Ergebnis exakt darstellbar ist.

    auch einfach nur falsch verstanden, ich mein ist ja nett und gut und alles, dass die Leute mir Tips geben was ich ja auch will, aber da ist so wenig Info dabei, dass ich auch nicht so recht weiß, wo ich das ansetzten soll.

    Du hast das Problem schon richtig verstanden.
    Grundsätzlich muss man sich ja bei Operationen mit Zahlen Gedanken machen, wann die Ergebnisse brauchbar sind. Bin ich als Nutzer in der Situation, dass Rechenergebnisse nicht zuverlässig korrekt sind, stellt sich die Frage,
    1. ob das tatsächliche Ergebnis statt dessen brauchbar ist (weil es z.B. eine Näherung darstellt wie bei Gleitkommazahlen),
    2. ob der entstehende Überlauf/Inexaktheit ggf. vor Ausführung der Rechnung erkannt und vermieden werden kann,
    3. wenigstens ein Fehler kommuniziert wird, damit der Anwender sich nicht auf falsche Daten verlässt.
    Nr. 2 ist z.B. für Integer in der Regel vergleichsweise einfach, insbesondere wenn der Wertebereich der Eingangsdaten bekannten Beschränkungen unterliegt.
    Dein rational genügt diesen Bedingungen bisher nicht. Die 2. Bedingung ist prinzipbedingt kaum erfüllbar, ein Abbruch per Exception ist folglich naheliegend. Option 1 sollte allerdings auch bedacht werden - zweiffellos hängt es allerdings von der Anwendung ab, ob ggf. Näherungsergebnis akzeptabel sein können. Ist nebenbei mathematisch ein recht interessante Sache (Stichwort Kettenbruchentwicklung).

    Praktisch würde ich vorliegenden Fall zunächst intern mit größeren Zahlen arbeiten. Wenn Zähler und Nenner je 32 bit benötigen, können wir sicher sein, das Zwischenergebnisse mit 64bit auskommen. Die Prüfung, ob ein Überlauf vorliegt, kann dann nach dem Normalisieren erfolgen.

    0

  • Hallo nochmals,

    @camper
    vielen Dank für deine Ausführung, das hat mir gleich viel mehr geholfen. Ich habe einen Prototyp für eine Funktion entwickelt, die 2 Rationals versucht zu addieren, und eine Exception wirft, wenn das normalisierte Ergebnis trotzdem überläuft (zumindest macht sie es in der Theorie und in wenigen Testfällen).

    Nun frage ich mich, ob das so in Ordnung ist, insbesondere das ganze Gecaste. Jedoch hat es nicht funktionert, als ich Zähler und Nenner nicht nach long long gecasted hab (overflow nicht erkannt, da schon passiert, weil das Ergebnis vermutlich noch als int evaluiert wurde, bevor es in den long long gesteckt wurde). Jedenfalls hab ich das mit 64bit so interpretiert, dass da ein long long her muss/soll/kann. (ich bin auf long long gekommen, da sizeof(long long) bei mir 8 ergibt)

    Hab gcd auf unsigned long long übertragen, damit ich auch die long longs normalisieren kann.

    Rational safe_add(const Rational& lhs, const Rational& rhs)
{
    long long lnum = static_cast<long long>(lhs.num);
    long long rnum = static_cast<long long>(rhs.num);
    long long lden = static_cast<long long>(lhs.denom);
    long long rden = static_cast<long long>(rhs.denom);

    long long n = lnum*rden + lden*rnum;
    long long d = lden * rden;

    // kürzen
    long long div = gcd(std::abs(n), std::abs(d));
    if (div > 1) {
        n /= div;
        d /= div;
    }

    if (n > maxint || d > maxint || n < minint || d < minint)
        throw std::runtime_error("Overflow while adding two rationals.");
    return Rational{ static_cast<int>(n), static_cast<int>(d) };
}

    Das Ganze könnte ich ja dann so benutzen:

    Rational& operator+=(const Rational& rhs)
{
    return *this = safe_add(*this, rhs);
}

    Vielleicht sollte ich Zähler und Nenner einfach public machen, das würde einige 'friend' Funktionen ersparen...

    Der Sache mit einen Bruch finden, der eventuell den theoretisch nicht Akzeptierten so annähert, dass man stattdessen diesen verwenden kann, werde ich mich anschließend widmen.
    Vielleicht ist das auch etwas änhliches, wie volkard mit dem brocot-stern-baum meinte (zumindest hab ich bei der Recherche gemeint da Parallelen zur Kettenbruchentwicklung zu finden).

    P.S.: Mir fällt grad so auf, wenn ich jetzt nicht eine Option einbaue, dass man das verwenden der Kettenbruchentwicklung abstellen kann (würde ich vermutlich schon), dann würde es doch praktisch nie zu Overflows kommen, oder?
    Ich mein, zu diesen riesigen Zählern und Nennern komme ich ja durch meinen momentanen naiven algo, der im Prinzip für jede Stelle die nächsthöhere Zehnerpotenz in den Nenner knallt, im Zähler wird die Zahl dementsprechend auch groß.

    0
  • ?

    falls das nicht allzu resourcen-kritisch ist, was du da mit den Brüchen vorhast, könnte man eine bignum library benutzen. Dann stellt sich das Problem erst gar nicht.

    0

  • die Funktion safe_add ist ja recht groß und Umfangreich. Würde es sich lohnen, einen check noch einzubauen, der nur safe_add verwendet, falls es so mit Integern zum Overflow kommen würde?:

    bool mul_is_safe(int lhs, int rhs)
{
    if (lhs > maxint / rhs || lhs < minint / rhs)
        return false;

    return true;
}

Rational& operator+=(const Rational& rhs)
{
    if (!mul_is_safe(*this.num, rhs.denom) ||
        !mul_is_safe(*this.denom, rhs.num) ||
        !mul_is_safe(*this.denom, rhs.denom)) {
                return *this = safe_add(*this, rhs);
     } else {
         this->num = this->num*rhs.denom + this->denom*rhs.num;
         this->denom *= rhs.denom;
         this->reduce();
         return *this;
    }
}

    Oder schenkt sich dadurch, dass 3 Mal mul_is_safe aufgerufen wird nicht viel?

    hhmm keiner antwortet. Jetzt stellt sich die Frage wieso...
    Zu unkonkret?
    Bin ich sowieso komplett falsch?
    Ist die Frage doof?
    Wurde sie schonmal irgendwo beantwortet und ich habs übersehen?
    Versteht keiner, was ich da mache(n) (will)?

    Ich finde das frustrierend. Aber egal. Ich hab 2 Bücher, das Internet, und meinen hoffentlich gesunden Menschenverstand. Das werd ich wohl irgendwie auch alleine hinbekommen.

    Bis dahin kann ich ja mal mich auf Anderes konzentrieren, z.B. Anwendung des brocot-stern-baums bzw der Kettenbruchentwicklung bei double-to-Rational

    Edit: Ich hab grad auf die harte Tour einen Bug in der Funktion gefunden. Die sieht nämlich echt alt aus, wenn ich mit 0 multiplizieren möchte.
    Jetzt muss ich überlegen, wie ich das behandle. Habs mir mal so überlegt:

    bool mul_is_safe(int lhs, int rhs)
{
    if (!lhs || !rhs) return true;
    if (lhs > maxint / rhs || lhs < minint / rhs) return false;
    return true;
}

    Das ist denke ich gut begründet, da eine Multiplikation mit 0 immer 0 ergibt.

    Also ich habe die Botschaft, dass hier niemand mehr schreibt, angenommen und entcheide das einfach selbst.

    Ich hab nochmal über das nachgedacht, was Nathan gesagt hat, ich kann ja einen Integer Overflow provozieren und wenn ich das Programm starte crasht es auch nicht gleich.

    Wenn das dann mit std::complex auch so ist, dann bin ich mir in meiner Entscheidung eigentlich ziemlich sicher: Die normalen Operatoren lass ich jetzt "unsicher". Aber ich lass mal die Funktionen drin, mit denen man "sicher" Addieren etc. kann.
    Da ich mich schon etwas in diese Kettenbruchentwicklung eingearbeitet habe, werde ich versuchen das noch in diese Funktionen einzubauen, dass sie bei passendem bool Wert einen Bruch ausgeben, der näherungsweise das gleiche Ergebnis ist, aber halt nicht overflowed.
    Das scheint für mich vorerst mal das Vernünftige zu sein, und ist ca. die Mitte zwischen den beiden Prinzipien.
    In dem Fall ist das Thema für mich gegessen, danke an alle 🙂

    0
Anmelden zum Antworten