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
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.
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
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.
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:
1 | /*
|
2 | @param[in,out] x Faktor und Resultat
|
3 | @param s Faktor
|
4 | @returns Nicht-Null bei Überlauf, sonst Null
|
5 | */
|
6 | int mul(int32_t *const x, const int32_t s) { |
7 | if (*x > 0) { |
8 | if ( (s > 0) ? |
9 | (*x > (INT32_MAX / s)) : |
10 | (s < (INT32_MIN / *x)) |
11 | )
|
12 | return 1; |
13 | }
|
14 | else if (*x < 0) { |
15 | if ( (s > 0) ? |
16 | (*x < (INT32_MIN / s)) : |
17 | (s < (INT32_MAX / *x)) |
18 | )
|
19 | return 1; |
20 | }
|
21 | |
22 | *x *= s; |
23 | return 0; |
24 | }
|
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.
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.
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.
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
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.
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 }
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)
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.