Forum: Compiler & IDEs Tipps und Tricks zum Thema Rechnen in ganzen Zahlen?


von Sepp (Gast)


Lesenswert?

Ich würde mich gerne etwas schlauer machen, was das Rechnen in ganzen 
Zahlen angeht. Compiler ist avr-gcc.

Oft kommt es ja vor, dass man etwas längliche Formeln hat. Man addiert, 
multipliziert, teilt, multipliziert wieder, teilt, usw. Nicht immer 
möchte man in float rechnen, weil es langsam ist und auch nicht allzu 
genau. Auf 64 Bit möchte man auch nicht gleich gehen.
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

Sofern der Wertebereich mitspielt, natürlich.
Gibt es noch andere "Tricks"? Vielleicht erscheint es banal, aber 
manches schreibt man einfach so hin und es wäre vielleicht 
verbesserungswürdig.

von Sebastian S. (amateur)


Lesenswert?

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.

: Bearbeitet durch User
von Sepp (Gast)


Lesenswert?

Genau das meinte ich. Danke für das gute Beispiel!

Wahrscheinlich kann man sagen, dass man die Zwischenergebnisse immer 
möglichst weit weg von 0 halten sollte (soweit es der Wertebereich 
zulässt), auch im Hinblick auf z.B. mehrfaches Dividieren?

von (Gast)


Lesenswert?

In TeX gibts eine Menge Zeug zu Arithmetik mit fixkomma-Zahlen: 
http://www.tug.org/texlive//devsrc/Master/texmf-dist/doc/generic/knuth/tex/tex.pdf 
ab Seite 38 ("Arithmetic  with  scaled  dimensions.").

von Sebastian S. (amateur)


Lesenswert?

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.

von Sebastian S. (amateur)


Lesenswert?

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.

von Frank M. (ukw) (Moderator) Benutzerseite


Lesenswert?

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.

von Helmut S. (helmuts)


Lesenswert?

> 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.

von foobar (Gast)


Lesenswert?

Runden wurde noch nicht erwähnt: a/b --> (a+b/2)/b

von C. A. Rotwang (Gast)


Lesenswert?

Sepp schrieb:

> Gibt es noch andere "Tricks"?

Ja, die fühlen an der Huschschüle ganze Lehrpläne. Nennt sich bspw. 
"Numerisches Rechnen für Ingenieure". Da werden auch Trivia wie 
Vermeidung von Rundungsfehlern/Stellenauslöschung durch angepasste 
Operatorenreihenfolge behandelt.

https://www5.in.tum.de/lehre/vorlesungen/konkr_math/SS_11/vorl/vor2.pdf
http://sim.mathematik.uni-halle.de/~arnold/courses/WiS05.m4/pdf/Skript_Section03.pdf
https://en.wikipedia.org/wiki/Kahan_summation_algorithm

Und es ist keine Trickserei sondern Grundlagen der Programmierung, die 
jeder beherrschen sollte, der seinen Computer zu mehr als zum Daddeln 
benutzt.

von abc.def (Gast)


Lesenswert?

Schaue mal bei 'vedische Mathematik' (Wikipedia, ich kann jetzt keinen 
Link setzen)
Ist mehr auf das Dezimalsystem. Für die Programmierung wahrscheinlich 
weniger zu gebrauchen. Aber interessant und eine mögliche Antwort auf 
deine allgemein gehaltene Frage.

von Martin H. (horo)


Lesenswert?

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

Gute Näherung: 22 / 7

von Sebastian S. (amateur)


Lesenswert?

@ 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.

: Bearbeitet durch User
von Peter D. (peda)


Lesenswert?

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ß.

von C. A. Rotwang (Gast)


Lesenswert?

Martin H. schrieb:
> Sebastian S. schrieb:
>> Pi = 3,14...
>
> Gute Näherung: 22 / 7

Nein. Für wenn soll das eine "gute" Näherung für π sein? Und wer braucht 
ohnehin eine Näherung??
Doch nur die Idioten , die bei der Programmierung nicht 3.1415926536 aus 
dem Kopf schreiben können, nicht wissen wo die Konstante ohnehin 
deklariert ist (bspw. math.h: #define M_PI) oder wie man ggf. 
nach-recherchiert (google!)

von Erwin D. (Gast)


Lesenswert?

abc.def schrieb:
> Schaue mal bei 'vedische Mathematik' (Wikipedia, ich kann jetzt keinen
> Link setzen)

https://de.wikipedia.org/wiki/Vedische_Mathematik_(Rechenmethoden)

von J. S. (engineer) Benutzerseite


Lesenswert?

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".

von c-hater (Gast)


Lesenswert?

Frank M. schrieb:

> Wermutstropfen: der gcc ist so schlau, dass er bei einer solchen
> Multiplikation das bereits automatisch macht.

Nur dann, wenn er das zur Compilezeit bereits weiss, er es also mit 
einer Konstanten zu tun hat.

> Bei entsprechender
> Optimierung muss man also gar nicht erst zu solchen Tricks greifen. Aber
> für Assembler-Programmierer kann das durchaus interessant sen.

Die können sogar noch deutlich mehr tun, nämlich vorhersehen, wann es 
weitere Möglichkeiten für eine derartige Optimierung gäbe, auch wenn 
keiner der Operanden eine Konstante ist. Wenn z.B. Messwert nur zehn 
Bits breit ist und zur Laufzeit mit einem variablen Faktor multipliziert 
werden muss, dann wird der erfahrene Assemblerprogrammierer im 
Unterschied zum Compiler die sich daraus ergebenden 
Optimierungsmöglichkeiten nutzen...

Und so ist das bei sehr vielen Optimierungen. Der Mensch ist immer 
besser als ein doofes Programm. Denn das kann auch nur, was ihm andere 
Menschen zuvor an Fähigkeiten eingehaucht haben. Die konnten aber 
unmöglich alles vorhersehen und ausserdem fehlt die Möglichkeit, dem 
Compiler sowas mitzuteilen. Außer man implementiert einen kompletten 
neuen Typ. Das ist aber absoluter Overkill, wenn man nur an einer Stelle 
eine Multiplikation optimieren will...

Asm rules... Gerade bei der Optimierung von fixed point Arithmetik 
gibt's wohl nix besseres...

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

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.

von Helmut S. (helmuts)


Lesenswert?

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.

von georg (Gast)


Lesenswert?

Sepp schrieb:
> Gibt es noch andere "Tricks"?

Es gab in der Frühzeit der Computer eine Berechnung der Mandelbrotmengen 
(die schönen Apfelmännchen-Bilder) basierend auf reiner 
Ganzzahlarithmetik, weil damals Fliesskomma zu langsam, wenn überhaupt 
verfügbar war. Ich fürchte, dieses Wissen ist mangels Bedarf 
verlorengegangen, aber vielleicht weiss ja jemand noch was. Es sind hier 
im Forum ja noch einige nicht ausgestorbene Dinosaurier unterwegs, 
ausser mir.

Georg

von Sepp (Gast)


Lesenswert?

Stimmt, und es gibt ja auch noch diese spezielle Wurzelfunktion von den 
Doom(?)-Entwicklern.

Ich meinte aber tatsächlich Rechnen mit ganzen Zahlen und habe jetzt 
auch mal ein Beispiel aus einem aktuellen Projekt:

int32_t a32, b32
uint16_t c16, d16, v16;

Folgendes soll berechnet werden:

v16 * a32 / c16 * d16 / b32

Das Ergebnis idealerweise gerundet auf eine ganze Zahl. Normal müsste 
man ja nach int64_t casten... Ich habe mich jetzt mit float begnügt und 
anschließend +0.5 zum Runden... ist sicher suboptimal.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.