Important announcement: there is an English version of this forum on
Datum:
Hallo Beim µC-Programmieren stoße ich immer wieder auf das Problem, dass ich eine formel habe die bei stupider Umsetztung zu überläufen führt. z.B.
a * b * c * d -------------- 3600 * 1000 |
Wenn die Maximalwerte bekannt sind lässt sich berechnen ob ein Overflow auftreten kann. a=10bit b=7bit c=8bit d=25bit Im Beispiel würde jetzt der Nenner überlaufen. Denn 10+7+8+25=40bit und somit größer als gängige 32bit ints. Durch Umformen der Formel könnte ein überlauf verhindert werden jedoch rundungsfehler hinzukommen. Gibt es eine Software die eine solche umforumung macht um den Fehler möglichst gering zu halten bzw möglichst wenige zusäzliche Divisonen hinzufügt oder shifts bevorzugt? Oder müsste ich soetwas selbst machen?
Datum:
Brain 2.0 würde ich da vorschlagen.
Datum:
Letztlich geht es nicht um ein Umformen im (entfernt) algebraischen Sinn, sondern man muss die Formel neu definieren. Variante a) Grösserer Datentyp für den Zähler verwenden. Variante b) Zwei Divisionen Variante c) So lassen, weil man z.B. Vorwissen hat, dass die Inputs nie genügend grosse werden oder weil man einen Overflow tolerieren bzw. abfangen kann. Hängt von der Situation ab. Diese Überlegungen kann dir kein Programm abnehmen.
Datum:
Flo schrieb: > > Im Beispiel würde jetzt der Nenner überlaufen. Denn 10+7+8+25=40bit und > somit größer als gängige 32bit ints. Oben ist der Zähler. Der Nenner ist unten. > Oder müsste ich soetwas selbst machen? Für einfache Sachen kannst du das schon selbst machen. Bei komplexen Sachen würde wohl auch so eine Software aussteigen.
Datum:
Aber bitte mit Sahne. Nein. Ehrlich. Das der Nenner überläuft kann ich nicht feststellen. Eher der Zähler. Der Nenner hat bloss 21 plus irgendwas Bit. Aber das Problem geht ja noch weiter. Entscheidest Du Dich dafür, eine der Divisionen etwas vorzuziehen, was geschieht dann mit den Rundungsfehlern? Sind vielleicht die Werte von a,b,c oder d eingeschränkt auf bestimmte Zahlen die gemeinsame Teiler mit dem Nenner haben? Da kann man Dir ne Software für schreiben, aber willst Du das bezahlen?
Datum:
Noch nie was von muldiv gehört, muldiv(a*b*c,d,3600*1000) in deinem Falle. Aber wenn es ein 32bit CPU ist, dann einfach den uint64_t nehmen, long long oder wie er in der Toolchain heisst. Ist es ein AVR, ... muldiv. Bei vielen 32bit CPU impliziert der Befehlt muldiv 64bit Integer, da der Compiler 64bit Arithmetik beherrscht. Da gibt es Asm Libs, wie auch ev. eine generische C Implementation, sollte die Toolchain die Lib nicht haben.
Datum:
Du kannst versuchen, den Bruch vorher zu kürzen: http://de.wikipedia.org/wiki/Euklidischer_Algorithmus http://de.wikipedia.org/wiki/Steinscher_Algorithmus Wenn die Variablen im Zähler allerdings völlig beliebige Werte annehmen können, dann wird ein Überlauf nicht garantiert verhindert. Eine weitere Möglichkeit wäre es, dass du auf 64 Bit gehst. Für die Division wirst du allerdings wahrscheinlich eine eigene Vorschrift schreiben müssen. Aber dafür gibt es einige Beispiele im Web. Grüße, Markus
Datum:
Flo schrieb: > Gibt es eine Software die eine solche umforumung macht um den Fehler > möglichst gering zu halten bzw möglichst wenige zusäzliche Divisonen > hinzufügt oder shifts bevorzugt? Meines Wissens nicht. Es gibt Libraries für extreme Datentypen, die aber auf einem 8bit uC total fehl am Platz sind (zB bignum und GMP). Hier hast du aber im Nenner eine Konstante, die sich unter Umständen rauskürzen lässt. Ich suche dabei oft nach Zweierpotenzen, bzw. schau mir dazu die Konstanten im Binärsystem an und überlege mir, welche Werte überhaupt mit welcher Präzision vorliegen und was ich ohne echten Datenverlust verwerfen kann. Bsp. Messwerte vom ADC, von den nominell 10 Bit ADC reichen 8 bit gemittelt/min/max völlig aus.
Datum:
ups Bezeichnung von Nenner und Zähler vertauscht xD Dass/wie ich mit händischem umstellen der Formel auch zum Ziel komme ist klar. Ich will doch nur wissen ob es eine Software gibt dir mir das umstellen abnimmt/automatisiert. Wie in meinem 1. Post geschreiben sind die Maximalwerte der einzelnen Faktoren bekannt. 64bit integer werden von der verwendeten Toolchain im C modus leider nicht unterstüzt. :-/ Ob eine Umstellung auf den C++ modus möglich ist muss ich erst noch mit den Kolegen klären. Zum beweiß, dass mein Brain 2.0 funktioniert aber nach Entlastung sucht ;-)
x = a * b * d; //10 + 7 + 25 = 32 bit x >>= 8; //32 - 8 = 24 bit x *= c; //24 + 8 bit x /= (3600*1000) >> 8; |
Datum:
Verdammt man sollte nicht die hälfte abschreiben und die andere hälfte aus dem kopf machen :-( a=10bit b=7bit c=8bit d=15bit und nicht 25 bit Dann passt auch der rest wieder zusammen.
Datum:
Hier eine stripped down muldiv Funktion, funktionioniert aber nur in
deinen
angegebenen Wertebereich mit der unten angegebenen Aufrufkonvention, nur
mit 32bit unsigned integers.
static uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c){
return (a * b)/c + ((a % c) * b) / c;
}
result= muldiv(a*c,b,d);
Datum:
a b c * d
--------------
3600 * 1000
a=10bit
b=7bit
c=8bit
d=15bit und nicht 25 bit
static uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c){
return (a/c)*b + ((a%c)*b)/c;
}
result= muldiv(a*c*d,b,3600*1000);
Beitrag #2689836 wurde von einem Moderator gelöscht.
Autor:
Simon K.
(simon)
Datum:
Was genau soll der sinn von muldiv jetzt sein? Hab das bisher im meinem Leben noch nie benötigt, bzw. gekannt. Und ich hab schon einige Fixkommaformeln umgestellt um Überlaufe zu vermeiden und gleichzeitig eine benötigte Genauigkeit einzuhalten.
Datum:
Simon K. schrieb: > Was genau soll der sinn von muldiv jetzt sein? Hab das bisher im meinem > Leben noch nie benötigt, bzw. gekannt. Und ich hab schon einige > Fixkommaformeln umgestellt um Überlaufe zu vermeiden und gleichzeitig > eine benötigte Genauigkeit einzuhalten. muldiv hat mich jetzt auch mal interessiert. Diesen Link hier finde ich dazu interessant: http://blogs.msdn.com/b/oldnewthing/archive/2012/0...
Datum:
@ Flo (Gast) >a b c * d >-------------- > 3600 * 1000 >Wenn die Maximalwerte bekannt sind lässt sich berechnen ob ein Overflow >auftreten kann. >a=10bit >b=7bit >c=8bit >d=15bit >Im Beispiel würde jetzt der Nenner überlaufen. Denn 10+7+8+15=40bit und >somit größer als gängige 32bit ints. >Durch Umformen der Formel könnte ein überlauf verhindert werden jedoch >rundungsfehler hinzukommen. Jo. >Gibt es eine Software die eine solche umforumung macht um den Fehler >möglichst gering zu halten bzw möglichst wenige zusäzliche Divisonen >hinzufügt oder shifts bevorzugt? Siehe Festkommaarithmetik. Die 1000 durch 1024 ersetzen in Form von.
1000 = 1024 / 1.024 a * b * c * d -------------- 1024 * 3515 |
-> C
x = a * b * d; //10 + 7 + 15 = 32 bit x >>= 10; //32 - 10 = 22 bit x *= c; //22 + 8 = 30 bit x /= 3600; //30-12 = 18 Bit |
Damit hat man den Rundungsfehler minimiert, wenn man sich nur auf uint32
Zahlen beschränken will. Achtung, in den Rechungen müssen die
Eingangsvariablen 32 Bit sein oder jede auf 32 Bit gecastet werden!
>Oder müsste ich soetwas selbst machen?
Jo.
Datum:
Simon K. schrieb: > Was genau soll der sinn von muldiv jetzt sein? Der von Chris gepostete Ausdruck (a / c) * b + ((a % c) * b) / c (1) liefert exakt das gleiche Ergebnis wie (a * b) / c (2) Dabei wird keines der Zwischenergebnisse größer als das Gesamtergebnis. Wenn also das erwartete Ergebnis in 32 Bit passt, kann der Ausdruck (1) problemlos in 32-BitArithmetik berechnet werden, während beim Ausdruck (2) zur Vermeidung eines Überlaufs bei der Berechnung von a * b 64-Bit-Arithmetik erforderlich ist. Das Verfahren ist vor allem dann interessant, wenn die Einzelvariablen schon die maximale Bitbreite der verwendeten Arithmetik-Bibliothek nutzen. Dann müssten bei der Berechnung von (2) a und/oder b vor der Multiplikation erst herunterskaliert werden, was aber die Genauigkeit verschlechtert. Bei (1) besteht dieses Problem nicht. Beispiel: a = 1023 b = 127 c = 255 d = 32767 Mit 40-Bit-Arithmetik:
a * b * c * d / 3600000 = 301546 (korrekt) |
Mit 32-Bit-Arithmetik:
a * b * c * d / 3600000 = 898 (falsch wegen Überlauf) |
Mit 32-Bit-Arithmetik und Skalierung (s. Falks Beitrag):
(a * b * d >> 10) * c / 3600 = 294478 (ungenau) |
Mit 32-Bit-Arithmetik und Skalierung (etwas optimiert):
(a * b * d >> 8) * c / 14062 = 301556 (immer noch etwas ungenau) |
Mit 32-Bit-Muldiv (a, b und d werden zu einem Faktor zusammengefasst):
a*b*d / 3600000 * c + a*b*d % 3600000 * c / 3600000 = 301546 (korrekt) |
Edit: Mit 32-Bit-Arithmetik und Skalierung (noch etwas optimiert):
(a * b * d / 288) * c / 12500 = 301546 (korrekt) |
Aber nicht immer. Für d = 74 (a, b und c wie oben):
(a * b * d / 288) * c / 12500 = 680 (korrekt wäre 681) |
Immerhin scheint dieser Ausdruck einen maximalen Fehler von nur -1 zu haben. Die Muldiv-Funktion rechnet aber immer richtig.
Datum:
Warum seid ihr alle so darauf verbissen mir das Beispiel händisch zu lösen? Ihr könnt natürlich weitermachen solange ihr spass daran habt ;-) Ich wollte eigentlich wissen ob es etwas gibt das mir diese Aufgabe abnimmt. So wie es aussieht gibt es das nicht oder keiner kennt es. :D
Datum:
Die SW gibt es, nur für solche einfache Formeln ungeeignet. Diese SW sind extrem Benutzerunfreundlich und basieren entweder auf numlib oder mathlab. Zudem ist dann die Wartung sowie Portierung der Programme sehr schwierig.
Datum:
Flo schrieb: > Warum seid ihr alle so darauf verbissen mir das Beispiel händisch zu > lösen? Ihr könnt natürlich weitermachen solange ihr spass daran habt ;-) > > Ich wollte eigentlich wissen ob es etwas gibt das mir diese Aufgabe > abnimmt. Gibt es, nämlich das Forum hier ;-) > So wie es aussieht gibt es das nicht oder keiner kennt es. :D Ich habe mal von etwas Derartigem gehört, weiß aber nicht mehr, wie es heißt und bin auch nicht sicher, ob es wirklich diese Sorte Aufgaben löst. Wenn ich mich recht erinnere, ist es ein Matlab-Modul (entweder von MathWorks selber oder von einem Drittanbieter), mit man man Matlab-Code mit Gleitkommaarithmetik weitgehend automatisch in C-Code mit Festkommaarithmetik übersetzen kann. Wahrscheinlich muss man noch irgendwo die Wertebereiche der Variablen und die gewünschte Genauigkeit angeben. Ich habe das Tool aber selbst nie verwendet, deswegen kann ich nicht viel dazu erzählen. Ich würde so einem Tool aber nicht blind vertrauen, denn — wie dieser Thread zeigt — gibt es viele unterschiedliche Wege zum Ziel, und gerade in der Mikrocontrollerwelt muss oft der beste Kompromiss aus Rechengenauigkeit, Laufzeit und Programmgröße gefunden werden, was keine triviale Aufgabe ist. Warum sollte ein Programm die Aufgabe besser lösen können als ich selbst? Bis ich so viel Vertrauen in das Tool erlangt hätte, dass ich ihm auch wichtige Aufgaben übertragen würde, hätte ich wahrscheinlich tausende Zeilen Code manuell umgestrickt und wüsste dann im Falle von Fehlern in den Ergebnissen wenigstens gleich, wo ich suchen muss :) Aber such mal im Matlab-Umfeld nach so einem Tool, vielleicht wirst du ja fündig.
Datum:
Flo schrieb: > Ich wollte eigentlich wissen ob es etwas gibt das mir diese Aufgabe > abnimmt. P. M. hat doch eine passende Antwort gegeben: Nämlich "hängt von der Situation ab". Vielleicht kann man geschickt umstellen. Vielleicht kommt man aber auch, aufgrund der schieren Größe der zu verarbeitenden Zahlen, nicht umhin einen größeren Datentyp zu verwenden, z.B. 64-bit. Vielleicht braucht man im Extremfall sogar arbitrary-precision arithmetic. Was Du willst, müsste ja im Endeffekt auch eine Art Code-Generator beinhalten. Ich bezweifle dass es sowas gibt, zumindest wenn man alle möglichen auftretenden Fälle damit abdecken wollte.
Datum:
Yalu X. schrieb: > (a / c) * b + ((a % c) * b) / c (1) > > liefert exakt das gleiche Ergebnis wie > > (a * b) / c (2) > > Dabei wird keines der Zwischenergebnisse größer als das Gesamtergebnis. > Wenn also das erwartete Ergebnis in 32 Bit passt, kann der Ausdruck (1) > problemlos in 32-BitArithmetik berechnet werden, während beim Ausdruck > (2) zur Vermeidung eines Überlaufs bei der Berechnung von a * b > 64-Bit-Arithmetik erforderlich ist. Aber was ist, wenn z.B. a = 359000 b = 24000 c = 360000 ist? Das Ergebnis von a*b/c passt in 32-Bit, aber der Zwischenschritt (a%c) * b liefert einen Overflow. Oder habe ich mich da vertan? Markus
Datum:
Markus D. schrieb: > Aber was ist, wenn z.B. > a = 359000 > b = 24000 > c = 360000 > ist? Das Ergebnis von a*b/c passt in 32-Bit, aber der Zwischenschritt > (a%c) * b liefert einen Overflow. Oder habe ich mich da vertan? Nein, du hast völlig recht, das habe ich übersehen. Damit Muldiv anwendbar ist, müssen also zwei Bedingungen erfüllt sein: Sowohl das Ergebnis a * b / c als auch das Zwischenergebnis (a % c) * b müssen im gewählten Wertebereich darstellbar sein. Eine hinreichende Bedingung für letzteres ist, dass (c - 1) * b darstellbar ist. Dröselt man das Beispiel so auf, wie ich es oben beschrieben habe, ist zum Glück :) auch die zweite Bedingung erfüllt.
Datum:
Ich würde sagen, wenn (a % c) * b in 32 Bit passt, dann passt auch a * b in 32 Bit und dann kann man muldiv auch ganz weglassen. Denn a % c kann ja höchstens a als Ergebnis haben. Markus
Datum:
Die gepostete Muldiv ist wie geschrieben eine reduzierte Muldiv welche
im vom Poster notwendigen Bitbreite funktioniert.
Mit hoher Warscheinlichkeit kenn der verwendete Compiler auch muldiv.
Ansonsten hier eine Basis einer richtigen muldiv welche man als
Basis für einen Port hernehmen kann. Man muss aber wissen, wie man
das 64bit Resultat aus der 32bit Multiplikation rausbekommt.
/***********************************************************************
* MulDiv (KERNEL32.@)
* RETURNS
* Result of multiplication and division
* -1: Overflow occurred or Divisor was 0
* FIXME! move to correct file
*
* @implemented
*/
INT
WINAPI
MulDiv(INT nNumber,
INT nNumerator,
INT nDenominator)
{
LARGE_INTEGER Result;
LONG Negative;
/* Find out if this will be a negative result */
Negative = nNumber ^ nNumerator ^ nDenominator;
/* Turn all the parameters into absolute values */
if (nNumber < 0) nNumber *= -1;
if (nNumerator < 0) nNumerator *= -1;
if (nDenominator < 0) nDenominator *= -1;
/* Calculate the result */
Result.QuadPart = Int32x32To64(nNumber, nNumerator) + (nDenominator
/ 2);
/* Now check for overflow */
if (nDenominator > Result.HighPart)
{
/* Divide the product to get the quotient and remainder */
Result.LowPart =
RtlEnlargedUnsignedDivide(*(PULARGE_INTEGER)&Result,
(ULONG)nDenominator,
(PULONG)&Result.HighPart);
/* Do the sign changes */
if ((LONG)Result.LowPart >= 0)
{
return (Negative >= 0) ? Result.LowPart :
-(LONG)Result.LowPart;
}
}
/* Return overflow */
return - 1;
}
Datum:
Man kann auch BCD rechnen bzw. 4 Bit Hex. Halt wie auf dem Papier per Hand. Dann kannst du soviele Stellen berechnen wie Speicher da ist. Dauert jedoch. Machen einige CAS Programme so oder Taschenrechner. Wenn die Laufzeit egal ist.
E-Mail-Benachrichtigung einschalten
Neu: Seitenaufteilung einschalten