Multiplikation/Division

[Walter T. (nicolas)]

Hallo zusammen,

ich bin wieder bei dem Versuch, eine Funktion "kugelsicher" zu bekommen. 
Naiv sieht die Funktion so aus:

    int32_t quotient_naive(int64_t cnt, int16_t z, int16_t n)
    {
        assert( z != 0 );
        assert( n > 0 );
        assert( cnt != INT64_MIN );

        /* Naiv: beruecksichtigt moeglichen Ueberlauf von cnt * 1000 oder cnt * 1000 * z nicht */
        int64_t res = cnt * 1000LL * z/n;

        /* Ergebnis saettigen auf int32. Die Symmetrie ist optional, es darf auch normal um
           INT32_MIN/INT_MAX geklemmt sein */
        if( res > INT32_MAX )
        {
            res = INT32_MAX;
        }
        else if( res < -INT32_MAX )
        {
            res = -INT32_MAX;
        }

        return res;
    }

Eine 64-Bit-Variable soll mit einer Variablen und einer Konstanten 
multipliziert und anschließend durch eine andere Variable dividiert 
werden. Das Ergebnis soll auf die Bitbreite des Rückgabewertes gesättigt 
werden, wobei es nicht von Belang ist, ob symmetrisch gesättigt wird, 
oder INT32_MIN mitgenommen wird.

Bis auf die drei Assertions, die ich hingeschrieben habe, gibt es keine 
Annahmen über den Wertebereich.

Mein erster Versuch, das Ganze "kugelsicher" zu bekommen, sieht so aus:

    int32_t quotient_1(int64_t cnt, int16_t z, int16_t n)
    {
        assert( z != 0 );
        assert( n > 0 );
        assert( cnt != INT64_MIN );

        if( ABS(cnt) >= INT32_MAX * n )
        {
            return SIGN(cnt) * INT32_MAX;
        }

        assert( ABS(cnt) < INT32_MAX * INT16_MAX );

        cnt *= z;

        if( ABS(cnt) >= INT32_MAX * n )
        {
            return SIGN(cnt) * INT32_MAX;
        }

        cnt *= 1000LL;
        cnt /= n;

        if( ABS(cnt) >= INT32_MAX )
        {
            return SIGN(cnt) * INT32_MAX;
        }
        else
        {
            return cnt;
        }
    }

 a) Habe ich etwas übersehen?
 b) Geht es besser? Wenn ja: Wie?

[Theor (Gast)]

Vielleicht sollte man ja lieber "manngedeckte" Funktionen schreiben. 
Oder "fischige Werte" mit "Bitnetzen fangen". Man könnte INT_MAX auch 
auf der "Kurveninnenseite überholen".

Sehr hübsch, - und mir liegen sie mehr -, sind auch Metaphern aus der 
Küche. Wie wärs mit "Zahlenschaum abschöpfen"?

[Nils (Gast)]

Magst Du ins einen Tip geben für welche Platform das sein soll, und 
welchen Compiler du benutzt?

Mit Compiler Extensions kann man da noch ein bischen zaubern.


Und: Ist der Faktor 1000 vorgegeben, oder kann da auch eine Power-of-two 
wie 1024 oder 65536 rein? Das macht u.U. die Berechnung etwas einfacher.

[Walter T. (nicolas)]

Nils schrieb:
> Magst Du ins einen Tip geben für welche Platform das sein soll, und
> welchen Compiler du benutzt?

Warum? int64 ist auf allen Plattformen, die das unterstützen, gleich, 
und int128 wird auf keiner mir bekannten Plattform unterstützt. Mit den



Nils schrieb:
> Und: Ist der Faktor 1000 vorgegeben, oder kann da auch eine Power-of-two
> wie 1024 oder 65536 rein?

Nein, dann wäre das ja einfach.

Im Prinzip läuft es ja darauf hinaus, den Vergleich a * b > c ? 
auszuführen, ohne die Multiplikation a * b auszuführen, weil diese 
überlaufen könnte. Wahrscheinlich gibt es ein Idiom

  (a * b > c) == a > (c + d)/b

Das würde die Sache vereinfachen. Aber ich knobele noch am d.



Nils schrieb:
> Magst Du ins einen Tip geben für welche Platform das sein soll, und
> welchen Compiler du benutzt?

Wenn Du darauf anspielst, ob __builtin_umull_overflow() zur Verfügung 
steht: Ja, tut es. Aber ich bin mir momentan nicht sicher, ob das die 
Sache vereinfacht.

[Theor (Gast)]

Walter T. schrieb:
> Nils schrieb:
>> Und: Ist der Faktor 1000 vorgegeben, oder kann da auch eine Power-of-two
>> wie 1024 oder 65536 rein?
>
> Nein, dann wäre das ja einfach.
>
> Im Prinzip läuft es ja darauf hinaus, den Vergleich a * b > c ?
> auszuführen, ohne die Multiplikation a * b auszuführen, weil diese
> überlaufen könnte. Wahrscheinlich gibt es ein Idiom
>
>   (a * b > c) == a > (c + d)/b
>
> Das würde die Sache vereinfachen. Aber ich knobele noch am d.


Aber wieso taucht da plätzlich d auf?

(a * b > c) == (a > c/b). Was Du vermutlich aber weißt.

Magst Du das 'd' mal erklären?