Elegante Prüfung des Produkts von vier Integer-Zahlen auf Grenzwert?

tecranovis

Hallo Forum,

ich bitte um Hilfe bei meinem folgenden Problem.

Ich habe vier Werte (unsigned, jede 32 bit lang) die ich multipliziere muss. Das Ergebnis muss dabei wieder in 32 bit unsigned 'passen'.

32 bit unsigned die größte Integer Zahl, die mein Compiler beherrscht.
Ein Überlauf kann natürlich auch schon bei der Multiplikation von a x b entstehen.

Wie kann nun ich in C elegant abbrüfen ob das Produkt von 2, 3 oder 4 Werten meinen Grenzwert( 2^32) erreicht bzw. überszeigt ?

Habe nur integer Aritmetik zur Verfügung, keine float-Werte und keine Berechnung von Logarithmus, damit wäre das evtl. einfacher zu lösen.

Mein Ansatz ist, die Potenzen des Produktes zu addieren und das dann auf >=32 zu prüfen. Beispiel:

a   x b    x c                  x d
256 x 4096 x 6000               x 50000
2^8 x 2^12 x 2^13 (aufgerundet) x 2^16 (aufgerunded)
-> Potenzen addiert ergeben 8+12+13+16 = 49 -> also Ergebnis > 32 -> Maximum wäre überschritten!

Wäre das ein Ansatz? Wie find ich dabei schnell die (aufgerundete) 2er Potenz zu einer Zahl, möglichst ohne extra Funktion oder rekursivem Aufruf?

Danke für jedem Tipp!

Printe

Das mit den Zweierpotenzen ist eine Abschätzung, die ziemlich ungenau sein kann, d.h. du kriegst Überläufe angezeigt, die gar keine sind.

Du könntest es so machen: Ein Produkt aus zwei Faktoren a und b (beide >= 1) ist genau dann nicht übergelaufen, wenn gilt:
Produkt >= a && Produkt >= b
Andersrum gesagt: Ein übergelaufenes Produkt aus zwei Faktoren ist kleiner als mindestens einer seiner Faktoren.

Das machst du bei vier Faktoren a, b, c und d nacheinander mit den Produkten
a * b
(a*b) * c
(a*b*c) * d

Da die Faktoren unsigned sind, ist die Bedingung (faktor >= 1) immer erfüllt bzw. nur der Fall 0 gesondert zu prüfen.

Printe

Eine andere Möglichkeit ist:

produkt = a * b * c * d
eins = produkt / d / c / b / a
if (eins == 1)
    ok
else
    // im else-Fall (Ueberlauf-Fall)
    // ist produkt kleiner als das 
    // Produkt der Faktoren,
    // und eins hat den Wert 0
    ueberlauf

Auch bei diesem Test muss vorher geprüft werden, ob einer der Faktoren a .. d == 0 ist, weil der Test in dem Fall nicht funktioniert.

tecranovis

Hallo Printe,

danke für deine schnellen und interessanten Antworten.

Ich möchte gerade verhindern, dass ein Wert überläuft. Auch bei der Logik, die auf den Grenzwert prüft.
Daher kann ich nicht einfach a*b oder a*b*c*d berechnen.

So ein Code war mal möglich In Zeiten von MISRA und diversen anderen Regelwerken, Anforderungen und Exceptions ist das in meinem Umfeld nicht mehr erlaubt.

Dass die Potenzen-Moethode Überläufe anzeigt, die keine sind ist natürlich ein Nachteil, der dazu führt, dass ich nicht den maximalen Wetebereich von 2^32 ausnutzen kann. Damit muss ich dann leben.

Vielleicht gibt es aber dafür noch eine Regelwerk-konforme Lösung ...

Naja, a*b > max ist erfüllt, wenn a > max/b und a, b != 0 sind. So könntest du das vorher testen, ist natürlich nicht gerade „billig” zu haben.

yahendrik

Du könntest auch die führenden Nullen addieren (Voraussetzung für einen Overflow ist natürlich, dass a oder b > 0xFFFF.

int clz(uint32_t x)
{
	static const unsigned char debruijn32[] = 
	{
		0, 31, 9, 30, 3, 8, 13, 29, 2, 5, 7, 21, 12, 24, 28, 19,
		1, 10, 4, 14, 6, 22, 25, 20, 11, 15, 23, 26, 16, 27, 17, 18
	};
	x |= x>>1;
	x |= x>>2;
	x |= x>>4;
	x |= x>>8;
	x |= x>>16;
	++x;
	return debruijn32[x*0x076be629>>27];
}

Wenn gilt:

clz(a) + clz(b) >= 32: definitiv kein Overflow.
clz(a) + clz(b) <= 30: Overflow sicher.

Bei clz(a) + clz(b) == 31 kann ein Overflow auftreten, dann hilft eben a > max/b.

Lohnt sich das? Müsste man mal messen...

Printe

tecranovis schrieb:

Vielleicht gibt es aber dafür noch eine Regelwerk-konforme Lösung ...

Welches Regelwerk gilt denn für dich, und was genau sagt es?

Und gibts denn zu diesem Regelwerk keine Knowledge-Base, in der du konforme Lösungen für alle möglichen Aufgaben finden kannst? Du bist doch sicher nicht der erste, der sowas machen soll.