Überlauf bei Multiplikation a priori erkennen

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.

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.

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.

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.

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.

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.

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.

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 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

1

#include <stdio.h>

2

3

typedef   short unsigned int uint16_t;

4

typedef   unsigned int uint32_t;

5

6

#define max(x,y)   ( (x) > (y) ? (x) : (y) )

7

int main (void)

8

{

9

  uint16_t a, b;

10

  uint32_t result;

11

12

  for( a = 0; a < 65535; a++ ) {

13

    for( b = 0; b < 65535; b++ ) {

14

      result = a * b;

15

      if( result > 65535 && !( max( a, b ) > (uint16_t)result ) )

16

        printf( "Gegenbeispiel  %d (%04x) * %d (%04x) = %d (%08x)\n", (int)a, (int)a, (int)b, (int)b, (int)result, (int)result );

17

    }

18

  }

19

}

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)
...

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:

1

uint32_t mulu32o(uint32_t x, uint32_t y) {

2

  uint32_t res = 0;

3

4

  if(y) {

5

    while(x) {

6

      if(x & 1) {

7

        if(y && y <= ~res)

8

          res += y;

9

        else {

10

          printf("Overflow\n"); // oder Errorflag setzen

11

          res = UINT32_MAX;

12

          break;

13

        }

14

      }

15

      x >>= 1;

16

      y <<= 1;

17

    }

18

  }

19

  return res;

20

}

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.

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)