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.
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
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?
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.").
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.
Runden wurde noch nicht erwähnt: a/b --> (a+b/2)/b
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.
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.
@ 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
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ß.
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!)
abc.def schrieb: > Schaue mal bei 'vedische Mathematik' (Wikipedia, ich kann jetzt keinen > Link setzen) https://de.wikipedia.org/wiki/Vedische_Mathematik_(Rechenmethoden)
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".
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...
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.
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
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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.