Tipps und Tricks zum Thema Rechnen in ganzen Zahlen?

Unter vielem anderem ist die Reihenfolge nicht ganz unwichtig.
So ist es z.B. sinnvoll erst zu multiplizieren und dann zu dividieren. 
Es kann aber auch nicht schaden, wenn die Größe dabei nicht 
überschritten wird.
Zum Bleistift: 100 Div 3 Mul 12
a)
100 Div 3 = 33
33 Mul 12 = 396
b)
100 Mul 12 = 1200
1200 Div 3 = 400
Wie man sehen kann, kommt im ersten Beispiel als größte Zahl 396 vor im 
zweiten aber 1200. Dass das Ergebnis, im zweiten Beispiel exakt ist, ist 
aber Zufall.

Du musst nicht unbedingt weit weg von der 0 bleiben, es sei denn Du 
werkelst unsigned herum.

Die Logik hinter meinem Beispiel ist: "Was weg, ist weg".
Die Addition, die Subtraktion und die Multiplikation sind "Verlustfrei".
Bei der Division geht aber leicht etwas verschüt', am wenigsten aber 
wenn die Zahlen so groß wie möglich sind.
Es kann sogar sein, dass es sinnvoll ist, zwischenzeitlich die Zahlen zu 
vergrößern (Faktor 10 oder 100 bzw. 16 oder 256) und am Ende erst wieder 
den Überstand durch Division zu herauszunehmen.
Beispiel:
 10 / 3 = 3
100 / 3 = 33
bei einer weiteren Rechnung ist natürlich 33 (wie man sehen kann) 
genauer als 3. Man sollte aber nicht vergessen, am Ende (an der 
richtigen Stelle) wieder durch 10 zu teilen.

Ist mir gerade eben erst eingefallen:
Pi = 3,14...
100 / Pi = 100   / 3   = 33 Oops
100 / Pi = 1000  / 31  = 32 schon besser, wenn man noch weiterrechnet.
100 / Pi = 10000 / 314 = 31 noch besser
Natürlich kann man nicht an beliebiger Stelle multiplizieren.

Auf bestimmten kleineren Prozessoren kann eine Multiplikation 
beschleunigt werden, indem man den Faktor in Zweierpotenzen zerlegt.

Beispiel: Multiplikation mit 80:

80 = 64 + 16

Statt

1

pos = 80 * lines;

kann

1

pos = (lines << 6) + (lines << 4);

durchaus schneller sein.

Wermutstropfen: der gcc ist so schlau, dass er bei einer solchen 
Multiplikation das bereits automatisch macht. Bei entsprechender 
Optimierung muss man also gar nicht erst zu solchen Tricks greifen. Aber 
für Assembler-Programmierer kann das durchaus interessant sen.

> Aber vielleicht gibt es ja Tricks zum Rechnen in z.B. (u)int32_t? Mir
ist klar, dass ich, bevor ich dividiere, möglichst erstmal
multipliziere, also

a*b/c anstatt a/c*b

Bei jeder größeren Anwendung mit Ganzzahlen muss man vor oder spätestens 
nach der zweiten Multiplikation das Ergebnis skalieren(schieben) um 
weniger als 32bit zu bekommen. Dieses gezielte schieben um trotzdem die 
maximal mögliche Auflösung zu erhalten erfordet deutlichen Zusatzaufwand 
in der Entwicklung im Vergleich zu Fließkomma-Arithmetik. Besonders 
ärgerlich wird es dann, wenn später plötzlich die Anforderung kommt, 
dass der Dynamikbereich einer der Faktoren doch größer ist und man bitte 
die Genauigkeit möglichst wenig verschlechtern soll. Dann muss man die 
ganze Schieberei nochmals überabeiten.

Sebastian S. schrieb:
> Pi = 3,14...

Gute Näherung: 22 / 7

@ Martin H.
Mir ging es nicht um die Zahl Pi, sondern darum: "je größer desto 
genauer".

Was vielleicht ein wenig unter den Tisch gefallen ist - wenn 
Rechenleistung wichtig ist - Mul 16 oder Mul 256 ist sehr viel schneller 
als Mul 10 bzw. Mul 100. Auch die Umkehr (Div) ist sehr viel schneller. 
Nur für's Auge "sieht" die 10/100 natürlich besser aus.

Übrigens: 22 / 7 ist in Ganzzahlarithmetik = 3
Erst beim Zerlegen in: Mul 22 und Div 7 kommst Du auf 31 aus dem obigen 
Beispiel.

Man sollte erstmal ganz genau überlegen, ob man sich den ganzen Hassle 
mit Ganzzahlen antun will oder nicht besser float nimmt. Die Compiler 
sind heute nicht mehr so schlecht und können auch gut ohne FPU rechnen.
Es ist zu kurz gedacht, daß ADC und DAC nur 16Bit haben und float 
unnötig wäre. Z.B. für eine PID-Regelung können die Koeffizienten oft 
eine hohe Dynamik benötigen, insbesondere wenn das zu regelnde System 
unbekannt ist und die Regelung selbst optimierend sein soll.
Ich hab mich da früher auch mit int abgequält und wurde mit 
Rundungsfehlern und Überläufen bestraft.

Auf einem 8-Bitter ist z.B. die Division in float schneller gegenüber 
int32_t, da sie nur 24 Bits berechnen muß.

C. A. Rotwang schrieb:
> Doch nur die Idioten , die bei der Programmierung nicht 3.1415926536 aus
... die diejenigen, die wie der TE in Ganzzahlarithmetik arbeiten und 
daher eine Darstellung mit kontrollierter Genauigkeit benötigen.


Sebastian S. schrieb:
> Ist mir gerade eben erst eingefallen:
> Pi = 3,14...

Beim Programmieren von Telespielen in der 8-Bit-Computer-Ära, war PI bei 
uns immer 201/64 mit einem Fehler von weniger als einem halben Prozent.

In späteren AMIGA-16-Bit-Zeit haben wir mit 3217:1024 gerechnet. Fehler 
irgendwas im Bereich einiger ppm.

Ähnliche Betrachtungen gibt es für e und andere Konstanten.

Viele Elektro-Musiker kennen meine Vereinfachung für den Abstand zweier 
Töne von 196/185. Ebenfalls Fehler im Bereich von ppm


Sepp schrieb:
> Ich würde mich gerne etwas schlauer machen, was das Rechnen in ganzen
> Zahlen angeht.

Wenn du tiefer in die Ganzzahlthematik einsteigen möchtest, schau mal 
nach "Restklassenrechnung".

Jürgen S. schrieb:
> Wenn du tiefer in die Ganzzahlthematik einsteigen möchtest,
> schau mal nach "Restklassenrechnung".

Das ist aber ne komplett andere Baustelle, weil Division komplett anders 
funktioniert.  Z.B: in Z/5Z

1/2 = 3

weil 2*3 = 1 mod 5.

Falls das Ganze in Richtung Fix-Komma-Zahlen geht, dann such mal mit 
Google nach

Q number format

Q ist die Anzahl der binären Stellen(Bits) hinter dem Komma.