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.
1
a * b * c * d
2
--------------
3
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?
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.
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.
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?
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.
Du kannst versuchen, den Bruch vorher zu kürzen:
http://de.wikipedia.org/wiki/Euklidischer_Algorithmushttp://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
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.
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
;-)
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.
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);
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);
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.
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/05/14/10304701.aspx
@ 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.
1
1000 = 1024 / 1.024
2
3
a * b * c * d
4
--------------
5
1024 * 3515
-> C
1
x=a*b*d;//10 + 7 + 15 = 32 bit
2
x>>=10;//32 - 10 = 22 bit
3
x*=c;//22 + 8 = 30 bit
4
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.
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:
1
a * b * c * d / 3600000 = 301546 (korrekt)
Mit 32-Bit-Arithmetik:
1
a * b * c * d / 3600000 = 898 (falsch wegen Überlauf)
Mit 32-Bit-Arithmetik und Skalierung (s. Falks Beitrag):
1
(a * b * d >> 10) * c / 3600 = 294478 (ungenau)
Mit 32-Bit-Arithmetik und Skalierung (etwas optimiert):
1
(a * b * d >> 8) * c / 14062 = 301556 (immer noch etwas ungenau)
Mit 32-Bit-Muldiv (a, b und d werden zu einem Faktor zusammengefasst):
1
a*b*d / 3600000 * c + a*b*d % 3600000 * c / 3600000 = 301546 (korrekt)
Edit:
Mit 32-Bit-Arithmetik und Skalierung (noch etwas optimiert):
1
(a * b * d / 288) * c / 12500 = 301546 (korrekt)
Aber nicht immer. Für d = 74 (a, b und c wie oben):
1
(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.
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
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.
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.
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.
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
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.
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
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;
}
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.
Thread beobachten
Seitenaufteilung abschalten