Überlauf bei Multiplikation a priori erkennen

[klaus (Gast)]

Hallo zusammmen,

ich Suche ein Verfahren, mit dem man feststellen kann, ob eine 
Multiplikation zweier Zahlen a und b (sagen wir jeweils 32-Bit unsigned) 
einen Überlauf produzieren wird oder nicht. Wie gesagt: Multiplikation, 
nicht Addition!

Jemand eine Idee?

Viele Grüße

[Karl H. (kbuchegg)]

Hmm

Im Grund läuft es doch darauf hinaus im Vorfeld von a * b zu berechnen
ob das Ergebnis von Maximal_Darstellbare_Zahl / a größer als b ist.
In deinem Beispiel

   if( ( 2_hoch_32_minus_1 / a ) > b )
     wird überlaufen

Nur hilft dir das in der Praxis meistens nichts, weil der Vortest länger 
dauern wird, als wie wenn du die Multiplikation einfach in uint64_t 
machst und dir die Bytes 'über' uint32_t ansiehst ob sie alle 0 sind.

[Bri (bri)]

Es reicht ja aus festzustellen, mit wieviel Bits die Zahlen kodiert 
sind. Wenn die Anzahl Bits der beiden Zahlen zusammenaddiert größer ist 
als die maximal mögliche Anzahl von Bits, dann gibts einen Überlauf. 
Aber wie schon mein Vorredner sagte, dauert das meistens länger, als die 
Multiplikation selbst. Außer der Prozessor hat einen Assemblerbefehl, 
der die führenden Nullen zählt.

[(prx) A. K. (prx)]

Wenn's nicht exakt sein muss, sondern die drei Zustände
   wird nicht - wird vielleicht - wird
ausreichen, dann reicht die Summe der Position des höchsten gesetzen 
Bits beider Operanden aus (ohne Vorzeichen betrachtet).

Wie schnell oder langsam das ist hängt davon ab, ob ein passender "find 
first set bit" Befehl vorhanden ist.

[Hc Z. (mizch)]

Du könntest die Positionen der höchstwertigen Bits (0 = LSB) für die 
beiden Zahlen herausfinden und addieren.  Ist das Ergebnis größer 31, 
hast Du Überlauf.

Ob das in einer realen Implementation so arg praktikabel ist, sei 
dahingestellt.

[klaus (Gast)]

T. B. schrieb:
> Aber wie schon mein Vorredner sagte, dauert das meistens länger, als die
> Multiplikation selbst. Außer der Prozessor hat einen Assemblerbefehl,
> der die führenden Nullen zählt.

Im Prinzip wäre es für mich auch i.O. die Multiplikation erst 
auszuführen und dann zu prüfen ob ein Überlauf aufgetreten ist. 
Allerdings habe ich keinen direkten Zugriff auf die Flags, man müßte es 
dann irgendwie anders erkennen.

A. K. schrieb:
> Wenn's nicht exakt sein muss, sondern die drei Zustände
>
>    wird nicht  kann  wird

Ja würde ausreichen, wobei ich kann dann einfach zu wird zählene würde 
um sicher zu sein.

Karl heinz Buchegger schrieb:
> Nur hilft dir das in der Praxis meistens nichts, weil der Vortest länger
>
> dauern wird, als wie wenn du die Multiplikation einfach in uint64_t
>
> machst und dir die Bytes 'über' uint32_t ansiehst ob sie alle 0 sind.

Geschwindigkeit wäre okay wenn etwas langsamer. Ich möchte primär 
wissen, ob ich dem Multiplikationsergbnis vertrauen kann. Allerdings 
int32u_t wäre der größte Datentyp den ich habe

[Karl H. (kbuchegg)]

A. K. schrieb:
> Wenn's nicht exakt sein muss, sondern die drei Zustände
>    wird nicht - wird vielleicht - wird
> ausreichen, dann reicht die Summe der Position des höchsten gesetzen
> Bits beider Operanden aus (ohne Vorzeichen betrachtet).

Wobei der Fall 'wird nicht' damit nicht 100% eindeutig feststellbar ist.

Bleiben wir bei 8 Bit und betrachten  127 * 2
127   das MSB ist an Bitposition 6
2     das MSB ist an Bitposition 1

6 + 1 = 7, passt also noch

Aber   127*3
127   MSB bei 6
3     MSB bei 1

In Summe wieder 7, aber diesmal passt es nicht mehr.

Ein Ergebnis von 7 müsste man daher in diesem Fall in die Grauzone 
'keine Ahnung' verlegen. Ich habs jetzt nicht weiter untersucht, aber 
die Frage ist doch: Bis zu welchem Summenergebnis kann ich der Sache 
noch trauen.

Das Problem ist für mich eines derjenigen bei dem man sich fragen muss: 
Bringt mir der Vortest soviel, das er sich lohnt, wenn er bei 100 
Operationen 99 mal umsonst gemacht wird und der eine Fall, den er mir 
optimiert, die 99 unnötigen Vortests aufwiegt.

[Karl H. (kbuchegg)]

klaus schrieb:

>> machst und dir die Bytes 'über' uint32_t ansiehst ob sie alle 0 sind.
>
> Geschwindigkeit wäre okay wenn etwas langsamer. Ich möchte primär
> wissen, ob ich dem Multiplikationsergbnis vertrauen kann.

Kannst du das etwas genauer ausführen?
In welchem Zusammenhang?

Die Sache ist die, das dies ein Problem ist, welches in seiner 
Allgemeinheit gar nicht so einfach zu lösen ist (vor allen Dingen dann 
nicht, wenn es auch noch akzeptabel schnell sein soll), in der Praxis 
aber meistens gar nicht so wild ist, weil man die Zahlenbereiche der 
beteiligten Operanden meistens ganz gut kennt bzw. einschätzen kann.

[(prx) A. K. (prx)]

Karl heinz Buchegger schrieb:

> Wobei der Fall 'wird nicht' damit nicht 100% eindeutig feststellbar ist.

Deshalb hatte ich ja den Fall "wird vielleicht" eingeführt. Wenn für die 
Summe wie in deinem Beispiel 7 herauskommt, dann ist das diese Grauzone, 
denn ein Bit kann immer hinzu kommen, aber nie 2.

[Sven P. (Gast)]

Wenn beide Zahlen vorzeichenlos sind, darf man den Überlauf in Kauf 
nehmen und a posteriori testen.
Bei vorzeichenbehafteten Zahlen ist ein Überlauf in C undefiniertes 
Verhalten und muss a priori festgestellt werden. Das Problem hatte ich 
kürzlich auch; Lösung:

/*
  @param[in,out] x           Faktor und Resultat
  @param s                   Faktor
  @returns                   Nicht-Null bei Überlauf, sonst Null
*/
int mul(int32_t *const x, const int32_t s) {
  if (*x > 0) {
    if ( (s > 0) ?
      (*x > (INT32_MAX / s)) :
      (s < (INT32_MIN / *x))
    )
      return 1;
  }
  else if (*x < 0) {
    if ( (s > 0) ?
      (*x < (INT32_MIN / s)) :
      (s < (INT32_MAX / *x))
    )
      return 1;
  }

  *x *= s;
  return 0;
}

CERT hatte dazu irgendwo mal ein paar ganz nette Überlegungen 
veröffentlicht, daran ist die Lösung oben auch angelehnt.
Ist allerdings nicht besonders effizient, zumindest nicht auf kleinen 
Prozessoren.

[klaus (Gast)]

Karl heinz Buchegger schrieb:
> Die Sache ist die, das dies ein Problem ist, welches in seiner
>
> Allgemeinheit gar nicht so einfach zu lösen ist (vor allen Dingen dann
>
> nicht, wenn es auch noch akzeptabel schnell sein soll), in der Praxis
>
> aber meistens gar nicht so wild ist, weil man die Zahlenbereiche der
>
> beteiligten Operanden meistens ganz gut kennt bzw. einschätzen kann.

Problem ist wie folgt:

Ich habe zwei int32u Zahlen a und b mit denen ich in einer Formel 
rechne. Diese hat die Gestalt y = (a * b) / c. Nun können a und b sehr 
groß werden (a ist eine Zeitspanne in nano Sekunden, b eine 
Taktfrequenz). Ich möchte nun wissen, ob das Ergebnis in y korrekt ist 
oder ob ein Überlauf aufgetreten ist. In Fall eines Überlaufs möchte ich 
für y den (bekannten) größten möglichen Wert benutzen. Es kommt 
eigentlich weniger auf die Geschwindigkeit des ganzen an.

[Karl H. (kbuchegg)]

A. K. schrieb:
> Karl heinz Buchegger schrieb:
>
>> Wobei der Fall 'wird nicht' damit nicht 100% eindeutig feststellbar ist.
>
> Deshalb hatte ich ja den Fall "wird vielleicht" eingeführt. Wenn für die
> Summe wie in deinem Beispiel 7 herauskommt, dann ist das diese Grauzone,
> denn ein Bit kann immer hinzu kommen, aber nie 2.

Wie gesagt: Ich hab mir das nicht weiter durch den Kopf gehen lassen, 
welche Grenzen da gelten müssten.

[klaus (Gast)]

Sven P. schrieb:
> CERT hatte dazu irgendwo mal ein paar ganz nette Überlegungen
>
> veröffentlicht, daran ist die Lösung oben auch angelehnt.
>
> Ist allerdings nicht besonders effizient, zumindest nicht auf kleinen
>
> Prozessoren.

Hallo Sven,

vielen Dank für die Antwort!
Das Verfahren werde ich probieren.


Kannst du mir vielleicht etwas zur Funktionsweise sagen oder wie es 
heißt damit ich danach suchen kann?

Viele Grüße

[Sven P. (Gast)]

Ja, sicher:
Link zum CERT-Artikel:
https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow?showComments=false

Funktionsweise: Macht genau das, was Karl-heinz benannt hat, aber halt 
auch für vorzeichenbehaftete Zahlen. Die Abfragen nach den Vorzeichen 
sind lediglich implizite Betragsfunktionen. Zudem wird (betragsmäßig) 
zwischen positivem und negativem Maximum unterschieden, da die beiden 
betragsmäßig nicht unbedingt gleich groß sind und die eine oder andere 
Multiplikation dann doch noch hinhaut.

Das blöde daran ist halt, dass die Betragsfunktion selbst auch 
überlaufen kann, darum wurde die durch das If-Gestrüpp ersetzt.

[klaus (Gast)]

Vielen Dank!


Wie ist das eigentlich wenn man unsigned Werte a posteriori auf einen 
Überlauf prüfen möchte. Funktioniert folgendes immer ?

y = a * b

if (max(a,b) > y)
{
  // Überlauf
}

[Karl H. (kbuchegg)]

klaus schrieb:
> Vielen Dank!
>
>
> Wie ist das eigentlich wenn man unsigned Werte a posteriori auf einen
> Überlauf prüfen möchte. Funktioniert folgendes immer ?
>
> y = a * b
>
> if (max(a,b) > y)
> {
>   // Überlauf
> }

Da ich dafür keinen formalen Beweis oder Gegenbeweis führen kann, hab 
ich auf dem PC schnell ein Testprogramm geschrieben, welches in der 
Domäne 16 Bit nach Gegenbeispielen sucht

#include <stdio.h>

typedef   short unsigned int uint16_t;
typedef   unsigned int uint32_t;

#define max(x,y)   ( (x) > (y) ? (x) : (y) )
int main (void)
{
  uint16_t a, b;
  uint32_t result;
  
  for( a = 0; a < 65535; a++ ) {
    for( b = 0; b < 65535; b++ ) {
      result = a * b;
      if( result > 65535 && !( max( a, b ) > (uint16_t)result ) )
        printf( "Gegenbeispiel  %d (%04x) * %d (%04x) = %d (%08x)\n", (int)a, (int)a, (int)b, (int)b, (int)result, (int)result );
    }
  }
}

leider wird es schon sehr bald fündig :-(

Gegenbeispiel  3 (0003) * 32768 (8000) = 98304 (00018000)
Gegenbeispiel  3 (0003) * 32769 (8001) = 98307 (00018003)
Gegenbeispiel  3 (0003) * 32770 (8002) = 98310 (00018006)
Gegenbeispiel  3 (0003) * 32771 (8003) = 98313 (00018009)
Gegenbeispiel  3 (0003) * 32772 (8004) = 98316 (0001800c)
Gegenbeispiel  3 (0003) * 32773 (8005) = 98319 (0001800f)
...

[Yalu X. (yalu) (Moderator)]

Je nachdem, wie lange die Division und die anschließende Multiplikation
auf dem Zielsystem dauert, könnte auch die Neuimplementierung der Multi-
plikation eine Lösung sein, z.B. so:

uint32_t mulu32o(uint32_t x, uint32_t y) {
  uint32_t res = 0;

  if(y) {
    while(x) {
      if(x & 1) {
        if(y && y <= ~res)
          res += y;
        else {
          printf("Overflow\n"); // oder Errorflag setzen
          res = UINT32_MAX;
          break;
        }
      }
      x >>= 1;
      y <<= 1;
    }
  }
  return res;
}

Die Routine erkennt den Überlauf während der Berechnung des Produkts und
setzt das Ergebnis ggf. auf die größte darstellbare Zahl. Alternativ
könnte auch ein Fehlerflag gesetzt werden, das im aufrufenden Programm-
teil abgefragt wird.

Wegen der nicht perfekten Optimierung durch den C-Compiler könnte aller-
dings die Builtin-Division plus -Multiplikation immer noch schneller
sein als die obige Multiplikation. Dann müsste man diese in Assembler
schreiben, um einen Geschwindigkeitsvorteil zu erhalten.

[Yalu X. (yalu) (Moderator)]

Autsch, Fehler!

Ich wollte in meinem letzten Beitrag die Überprüfung des Überlaufs von
y<<=1 besonders elegant lösen, was aber gewaltig nach hinten geschossen
hat. Die Behebung des Fehlers ist aber eine schöne Übungsaufgabe für
Interessierte ;-)

(habe gerade keine Zeit, das zu ändern und etwas intensiver zu testen)