Fehlerminimierung bei Integer-Rechnung

[Walter T. (nicolas)]

Hallo zusammen,

kennt jemand gute Literatur zum Thema Integer-Rechnung? Konkret geht es 
mir um die Fehlerminimierung. Dabei habe ich ein recht einfaches 
Problem:

Ich errechne einen Parameter per Integer-Division:

p = a/b*d (exakt)

wird zu

p = (a*d) ÷ b + e1 mit 0 <= e1 < 1.


Brauche ich die Umkehroperation:

d' = b/a*p (exakt)

wird das zu:

d' = (b*(p-e1)) ÷ a + e2 mit 0 <= e2 < 1,

d.h. mein Resultat d' ist grundsätzlich immer zu klein.

Vermutlich gibt es einen Offset, mit dem man diesen Fehler minimieren 
kann, so daß d' um das reale d schwankt und nicht grundsätzlich um 0...2 
zu klein ist.

Wie schon oben geschrieben: Ich bin nicht nur an der Lösung meines 
konkreten Problems interessiert. Für das konkrete Problem läßt sich das 
ja problemlos auf dem Papier machen: Die beiden Fehler-Terme ausklammern 
und es kommt heraus, daß der Fehler am kleinsten ist, wenn:

p = (a*d + b/2) ÷ b + e1 mit -1 <= e1 < 1 für d > 0

Lieber wäre mir Literatur, die sich mit diskret-numerischen Effekten 
dieser Art befaßt. Mit bekannte Literatur zum Thema Numerik befaßt sich 
nur mit Effekten, die bei float-Werten und numerische Verfahren 
auftreten.



Viele Grüße
W.T.

P.S: nicht über die Ausführlichkeit der Beschreibung der Division 
wundern - mir ist erst aufgefallen, wie offensichtlich die Lösung ist, 
als ich die Frage formuliert habe. Die Frage nach der Literatur bleibt 
aber bestehen.

[lux. (Gast)]

Dass bis jetzt noch keiner liegt wohl daran, dass dein Text recht 
verwirrt und verwirrend wirkt.

Ich kann dir auf die schnelle nicht mit Literatur helfen, aber dich in 
Richtung fixed point arithmethic verweisen.
Effektiv ist das die Technik deine Werte vor der Berechnung um Faktor x 
aufzublasen (aufpassen bei Multiplikationen und Divisionen) um 
Nachkommastellen, die du sonst verlieren würdest zu behalten. Nachdem 
alle Berechnungen fertig sind, dein Ergebnis wieder durch x zu 
dividieren => am Schluss hast du einen Fehler von -1 bis 0, wenn der 
Betrag des Fehler in der Rechnung zuvor kleiner als der Faktor x ist.

[Falk B. (falk)]

Die einfache Antwort lautet, siehe Festkommaarithmetik. Erst alle 
Multiplikationen (denn dort verlieert man keine Genauigkeit), dann alle 
Divisionen (dort verliert man Genauigkeit).

[Walter T. (nicolas)]

lux. schrieb:
> [...] aber dich in
> Richtung fixed point arithmethic verweisen. [...]

Falk B. schrieb:
> Die einfache Antwort lautet, siehe Festkommaarithmetik.


Festkommaarithmetik ist nicht das, was ich suche. Klar: Wenn ich 
entsprechend skaliere, verringert sich sowohl der Fehler durchs 
Abschneiden als auch der durchs Runden. Durch die "bessere" Auswertung 
der Division verringere ich meinen Fehler innerhalb meiner 
Genauigkeitsklasse (und bei meiner ursprünglichen Problemstellung ist 
genau das ausreichend).

Beides sind allerdings Ausprägungen des gleichen Themenfeldes, den ich 
mal als "Integer-Numerik" bezeichnen würde, und das vermutlich noch 
weitaus mehr enthält als Division. Leider finde ich dazu keine 
Übersicht. Über Integer-Mathematik findet man immer nur die gleichen 
Themenkomplexe:

 - Überlauf
 - Modulo-Operationen
 - Undefiniertheit bestimmter Operationen in C
 - Festkommaarithmetik
 - Grenzwerte

Mit dem Divisionsbeispiel von oben habe ich aber angeführt, daß es da 
auch noch andere interessante Themenkomplexe im Bereich der 
Computer-Integer-Mathematik gibt:
 - Fehlerrechnung
 - Näherungsverfahren
 - ... ?

Dazu suche ich Quellen.

[Eric B. (beric)]

https://de.wikipedia.org/wiki/Ring_(Algebra)
oder noch besser hier: https://en.wikipedia.org/wiki/Algebraic_structure
Letzteres aber im Anglosaxischen Sprachraum

Das sind die Grundlagen der Integerarithmetik.