int Berechnungen ohne ( Überlauf && Long )

[Moritz G. (mbydq2)]

Ich habe Polynome zu berechnen. Die Quellwerte und der Zielwert sind 
(unsigned) int. Das Ergebnis passt für alle Eingaben in int.
Wie kann ich sicherstellen, dass während der Berechnung nur '2 Byte 
werte'/'int' genutzt werden? Gibt es ein Programm, dass die Formeln 
umschreibt? Wie macht der ASM-Schreiber das?
Aktuell sehen meine Zeilen so aus:

int_tempA = (((int_1letztesA>>4)*(int_1letztesA>>4))*5>>5) + (3*int_1letztesA>>3);
int_tempB = int_1letztesB - 500;
int_tempB = (((int_tempB>>3)*(int_tempB>>3))>>6)*(int_tempB>>3);
int_tempB = (((((55*int_tempB)>>6)*39)>>8) + (int_1letztesB+500))>>1;

Das kostet aber viel Zeit sich jedes mal Gedanken zu machen wie man es 
am besten macht. Divisionen durch

$$\frac{a}{2^n}$$

ersetzen. Große Multiplikationen faktorisieren. Wertebereich immer voll 
ausnutzen. Mehrfachberechnungen Ausklammern/Vermeiden.

verwandte Themen:
Beitrag "Überlauf beim Rechnen oder erst beim speichern?"
Beitrag "Überlauf bei integer-Berechnung oder nicht??"

[Moritz G. (mbydq2)]

Moritz G. schrieb:
> Die Quellwerte und der Zielwert sind
> (unsigned) int.

Und so schnell geht es schief. Ich habe einen der Zielwerte als 
Zwischenwertspeicher genutzt, aber nicht geprüft ob die Variablen 
wirklich signed int waren. Innerhalb der Berechnung treten aber negative 
Werte auf.

Auch dies ist falsch da ein Überlauf passiert, sobald mit 55 
multipliziert wird:

int_tempB = (((int_tempB>>3)*(int_tempB>>3))>>6)*(int_tempB>>3);

int_tempB = (((((55*int_tempB)>>6)*39)>>8) + (int_1letztesB+500))>>1;

Es muss:

int_tempB = (((int_tempB>>3)*(int_tempB>>3))>>6)*(int_tempB>>3)>>6;

int_tempB = (((((55*int_tempB)>>6)*39)>>2) + (int_1letztesB+500))>>1;

oder

(55*(int_tempB>>6)>>6)*39

sein.
Nun habe ich sichergestellt, dass nur 15 bit genutzt werden.
Was macht der Compiler, wenn s_int*s_int*s_int berechnet werden muss? 
Eigentlich bräuchte er einen (3*15+1)bit>32bit Datentypen. 48bit Typen 
gibt es wohl nicht? Also nimmt er 64bit und das nennt sich für AVR 
LongLong ?
Wenn ich nach jeder Multiplikation caste bleibt es bei s_int ?

[Johann L. (gjlayde)]

Moritz G. schrieb:
> Ich habe Polynome zu berechnen. Die Quellwerte und der Zielwert sind
> (unsigned) int. Das Ergebnis passt für alle Eingaben in int.

Vielleicht hülf bereits eine andere Darstellunf des Polynoms.

Die gewählte Darstellung hat den Nachteil, daß auch dann, wenn das 
Endergebnis nicht aus dem Wertebereich fällt, dies für 
Zwischenergebnisse gelten kann.

Mit der o.g. Nebenbedingung bietet sich eine Darstellung mit 
Bernsteinpolynomen als Basis an anstatt 1,x,x²,x³ als Basis.
Der Basiswechsel ist einfach eine lineare Transformation die 
vorberechnet werden kann, da die Koeffizienten wohl bekannt sind.

Als x-Koordinaten der Kontrollpunkte ergeben sich damit

$$x_0, \tfrac23 x_0+\tfrac13 x_1, \tfrac13 x_0+\tfrac23 x_1, x_1$$

und da bekannt ist, daß die zugehörigen y-Koordinaten alle im Intervall 
[y0,y1] liegen, liegt das Kontrollpolygon komplett im durch
(x0,y0), (x0,y1), (x1,y1), (x1,y0)
aufgespannten Rechteck.

Dies wiederum bedeutet, daß, kein Zwischenergebnis überläuft -- falls 
man das Polynom nach De-Casteljau auswertet :-)

http://de.wikipedia.org/wiki/De-Casteljau-Algorithmus