Hallo zusammen, ich habe einen Bruch int32_t Z, int32_t N, bei dem Zähler und/oder Nenner 32 Bit breit sind. Der Zähler und Nenner sind schon teilerfremd, d.h. der Bruch ist maximal gekürzt, und normalisiert, d.h. der Nenner ist immer größer als 0. Jetzt suche ich den Bruch int16_t z, int16_t n, bei dem Zähler und Nenner kleiner als 16 Bit (vorzeichenbehaftet) sind, der den Bruch Z/N bestmöglich approximiert. Erster naiver Ansatz: n = INT16_MAX; aber es lässt sich für viele Brüche Z/N zeigen, dass es bessere Approximationen gibt. Jetzt bin ich bei vollständiger Enumeration des Suchraums, d.h. ich gehe den für den Nenner alle Zahlen von 1 bis INT16_MAX durch, prüfe ob der zugehörige Zähler (und der Zähler plus 1) einen kleineren Fehler als die bisherige Approximation liefert. Das Ganze muss nur dreimal beim Start meines STM32F446 laufen, die Laufzeit ist also nicht wahnsinnig kritisch, aber dominiert die Startzeit leider. Gibt es einen intelligenteren Algorithmus?
:
Bearbeitet durch User
Euklidischer Algorithmus? Ich bin mir gerade nicht sicher, ob der immer das Optimum liefert, aber auf jeden Fall sehr schnell gute Näherungen.
Yalu X. schrieb: > Euklidischer Algorithmus? Den kenne ich nur für die Ermittlung des größten gemeinsamen Teilers. Das ist auch tatsächlich ein vorab-Schritt, um das hier sicherzustellen: Walter T. schrieb: > Der Zähler und Nenner sind schon teilerfremd, > d.h. der Bruch ist maximal gekürzt, und normalisiert, d.h. der Nenner > ist immer größer als 0. Gibt es da eine Erweiterung zum Approximieren? (Ganzzahl-Arithmetik und Restklassenringe sind meine Achillesferse.)
:
Bearbeitet durch User
Ich hatte vergessen, auch das Stichwort "Kettenbruch" zu erwähnen. Diese beiden Artikel helfen dir evtl. weiter: https://de.wikipedia.org/wiki/Kettenbruch#Beste_N%C3%A4herungen https://de.wikipedia.org/wiki/Euklidischer_Algorithmus#Euklidischer_Algorithmus_und_Kettenbruchzerlegung
Du versuchst nun schon über sehr lange Zeit, haufenweise spezielle Würg-Arounds zu basteln, um float zu vermeiden. Das ist doch alles rein akademisch ohne jeden praktischen Nutzen. Hast Du wirklich soviel Langeweile? Ich war früher auch mal militanter float Gegner, hab dann aber gemerkt, daß selbst ein AT89C51 @12MHz reichlich Power hat, damit der Benutzer nicht die geringsten Laufzeitunterschiede merkt. Ich benutze inzwischen auch ausschließlich sprintf, sscanf, statt mir umständlich was selber zu basteln. Man braucht nur etwas Einarbeitungszeit in die Formatstrings, aber es lohnt sich. Man kann die Doku ja jederzeit im Web nachschlagen. Walter T. schrieb: > Das Ganze muss nur dreimal beim Start meines STM32F446 laufen, die > Laufzeit ist also nicht wahnsinnig kritisch, aber dominiert die > Startzeit leider. Es gibt dafür 2 einfache Tricks: 1. Man startet die Mainloop sofort und läßt die Berechnung im Hintergrund laufen, z.B. ein Timerinterrupt führt kleine Häppchen davon aus. 2. Man läßt die Rechnung nur einmal laufen und speichert die Ergebnisse im EEPROM/Flash ab.
Peter D. schrieb: > Du versuchst nun schon über sehr lange Zeit, haufenweise spezielle > Würg-Arounds zu basteln, um float zu vermeiden. Float versuche ich nicht zu vermeiden. Float ist super. Mit float und double fühle ich mich zuhause. Ich versuche double (möglichst, nicht komplett) zu vermeiden. Und an manchen Stellen ist es mir wichtig, dass der Fehler nicht anwächst. Da komme ich um Integer nicht herum. Das Ergebnis wird als Bruch in Integer z/n benötigt. Wenn die Bestimmung einer möglichst exakten Approximation des Bruches Z/N über den Zwischenschritt einer Approximation in double geht, ist das absolut okay. Wird ja eh nur dreimal gerechnet. Mit fällt da nur auch kein besserer Algorithmus als vollständige Enumeration ein. Peter D. schrieb: > 2. Man läßt die Rechnung nur einmal laufen und speichert die Ergebnisse > im EEPROM/Flash ab. Kann man so machen. Ist eine Notlösung. Sie gefällt mir deshalb nicht besonders, weil ein sehr lokales Problem ( Z/N -> z/n ) zu einem verteilten Problem mit zahlreichen Abhängigkeit ausweitet. Wäre ich verzweifelt, würde ich das wohl so machen. Peter D. schrieb: > 1. Man startet die Mainloop sofort und läßt die Berechnung im > Hintergrund laufen, z.B. ein Timerinterrupt führt kleine Häppchen davon > aus. Das ginge notfalls auch. Beim Systemstart arbeitet man langsam mit dem exakten Bruch Z/N und schaltet dann um auf die Näherung, sobald sie vorliegt, und aktiviert erst dann die Zusatzfunktionalität, die durch die freiwerdende Rechenleistung ermöglich wird. Oder lebt eben am Anfang mit einer etwas zäheren Bedienbarkeit. Aber auch das sind hauptsächlich erst einmal mehr Abhängigkeiten für ein sehr lokales Problem. Peter D. schrieb: > Das ist doch alles rein akademisch ohne jeden praktischen Nutzen. Das ist möglich. Aber der Vorteil an einem reinen Hobbyprojekt ist, dass ich meinen Zeitaufwand gegenüber niemandem rechtfertigen muss, sondern mir einfach jeweils die interessanteresten Teilaspekte aussuchen kann. Yalu X. schrieb: > Ich hatte vergessen, auch das Stichwort "Kettenbruch" zu erwähnen. Diese > beiden Artikel helfen dir evtl. weiter: Danke! Ich denke, dass muss ich sowohl mal ausgeschrieben als auch einmal programmiert haben, um das komplett verstanden zu haben. Mit Kettenbrüchen hatte ich bislang noch keine Berührpunkte. Nachtrag: Auf den ersten Blick sieht das sogar sehr gut aus. Da kann ich mir die "Vorkonditionierung" (größter gemeinsamer Teiler) sogar sparen und direkt über die Kettenbruchzerlegung gehen. Aber das ist etwas für später. Die Kaffeepause ist um.
:
Bearbeitet durch User
Walter T. schrieb: > Wird ja eh nur dreimal gerechnet. Mit fällt da nur auch kein > besserer Algorithmus als vollständige Enumeration ein. Von welcher Laufzeit sprechen wir hier? Die 3·2¹⁶ Schleifendurchläufe gehen doch auf dem STM32F446 (der ja keine lahme Ente ist) sicher so schnell, dass der Anwender kaum etwas davon mitbekommt.
Yalu X. schrieb: > Von welcher Laufzeit sprechen wir hier? Bitte nicht hauen! Ich weiß es noch nicht. Ich habe es noch nicht ausprobiert. Bei vollständiger Enumeration treibt mich eher eine Phobie.
Yalu X. schrieb: > Von welcher Laufzeit sprechen wir hier? Von ca. 28 Millisekunden. (28 Sekunden bei 1000 Durchläufen mit Zufallszahlen ohne Abbruch bei Fehler=0). Also schnell genug. Das heißt jede Verbesserung durch einen anderen Algorithmus ist rein Interessehalber.
Walter T. schrieb: > Das heißt jede Verbesserung durch einen anderen Algorithmus ist rein > Interessehalber. Hab's mal mit den Kettenbrüchen versucht, aber nur an wenigen Beispielen getestet. Der Code könnte also noch Bugs, evtl. sogar grobe Denkfehler enthalten. Der Rechenaufwand steigt logarithmisch mit dem Nennerlimit. Bei einem Nennerlimit von 65536 werden maximal 25 Schleifendurchläufe benötigt.
Angehängte Dateien:
Yalu X. schrieb: > Hab's mal mit den Kettenbrüchen versucht, aber nur an wenigen Beispielen > getestet. Danke für's Probieren! Ich führe mir das direkt mal zu Gemüte. Ehrlich gesagt ist mir der Denkansatz auch viel wichtiger als eine korrekte Implementierung. Wie ich ja schon oben schrieb, ist dieser Teil der Mathematik definitiv nicht meine Stärke. Ich habe mal versucht, die Vorgehensweise bei Kettenbruchzerlegung und einer daraus zu bestimmenden Näherung zu verstehen, komme aber auf keinen grünen Zweig. a) Ich mache eine Kettenbruchzerlegung des Bruchs Z/N. Da das rational ist, wird es auf jeden Fall terminieren, weil irgendwann der Rest 0 ist. Ich habe dann eine vorher nicht bestimmbare Anzahl an Quotienten q_0 bis q_n und zwei Reste r_n und r_n+1. Alle anderen Reste benötige ich für meinen Kettenbruch nicht. Wenn ich das richtig sehe, muss ich alle q_i und die letzten beiden r_i speichern, um den ursprünglichen Bruch exakt als Kettenbruch darzustellen. b) Wenn ich das alles ausmultipliziere, habe ich wieder den kompletten Bruch wie vorher. Also muss ich wohl irgendwann früher abbrechen. Aber woher weiß ich, wann? Ich nehme an, wenn der letzte Rest r_i in die gewünschte Größenordnung kommt, weil das ja später der Hauptnenner ist. Dann aber: c) Wenn Z und N teilerfremd ist, sollte der Algorithmus doch automatisch im dritten Schritt terminieren, oder habe ich da einen Denkfehler? Aber wenn ich ohnehin nur drei Schritte habe - was kann ich dann weglassen, ob gröber zu werden (respektive einen kleineren Nenner zu bekommen)? Vielleicht klären sich Teile daraus aus dem Quelltext. Danke für den Ansatz!
:
Bearbeitet durch User
Walter T. schrieb: > 1 bis INT16_MAX Du brauchst nur den Bereich int16_MAX/2 bis INT16_MAX und nur für die größere Zahl durchlaufen. Ersparnis: 50%
A. S. schrieb: > Du brauchst nur den Bereich int16_MAX/2 bis INT16_MAX [...] durchlaufen. Warum? Warum kann die perfekte Näherung nicht zwischen 1 und INT16_MAX/2 liegen? (Oder vielleicht auch: Wenn die perfekte Näherung zwische 1 und INT16_MAX/2 liegt - woher kann ich sicher sein, dass sie in der anderen Hälfte ein zweites Mal vorhanden ist?) Nachtrag: Hat sich geklärt. Ich lasse die Frage mal aus didaktischen Gründen stehen. Für jede Zahl in der unteren Hälfte gibt es die doppelte in der oberen Hälfte. Da Z und N aber teilerfremd sind, brauche ich erst gar nicht zu kürzen versuchen.
:
Bearbeitet durch User
Walter T. schrieb: > A. S. schrieb: >> Du brauchst nur den Bereich int16_MAX/2 bis INT16_MAX [...] durchlaufen. > > Warum? Warum kann die perfekte Näherung nicht zwischen 1 und INT16_MAX/2 > liegen? Kann sie. Sie liegt dann aber "auch" im oberen Bereich. Du kannst es noch weiter eingrenzen: Bei Zahlen > 1 interessiert nur fraktionale Teil. Beispiel: Bei 3,745 und Nenner n ist der Zähler immer 3n+z1. z1/n kannst Du somit getrennt suchen. für z1 bleibt aber nur ein Zahlenbereich von 0.. INT16_MAX/3,745 Und davon wieder nur die obere Hälfte.
A. S. schrieb: > [...] und nur für die größere Zahl durchlaufen. Daran knobele ich noch. Ich mache am Anfang der Einfachheit halber alles vorzeichenlos. Wenn ich n durchlaufe, habe ich als Näherung für z zur Auswahl: z = Z * n/N; z = Z * n/N + 1; Meine Fehlerbedingung ist: err = Z*n - z*N (oder umgekehrt, falls z*N > Z*n). Warum kann es nur der größere Wert sein?
:
Bearbeitet durch User
A. S. schrieb: > für z1 bleibt aber nur ein > Zahlenbereich von 0.. INT16_MAX/3,745 Und davon wieder nur die obere > Hälfte. Sorry, das ist falsch.
Yalu X. schrieb: > Der Code könnte also noch Bugs, evtl. sogar grobe Denkfehler > enthalten. Für Z = 40973 und N = 29147 kommen z = -24563 und n = 29147 heraus. Mit vollständiger Enumeration komme ich auf z = 9067, n = 6450. Auffällig an dem Beispiel ist, dass Zähler und Nenner recht klein sind. Zuerst vermutete ich, dass das an der Abbruchbedingung liegt, die nur den Nenner sicherstellt. Aber tauscht man Zähler und Nenner entsprechend nach dem Größeren, werden einfach die Eingangswerte durchgereicht. Ich habe aber noch nicht verstanden, wie die Abbruchbedingung Optimalität sicherstellen soll, deswegen suche ich noch. Die vollständigen Enumeration ohne die oben vorgeschlagenen Optimierungen ist recht primitiv (siehe Anhang). Mit den Optimierungen ändert sich meßbar aber nicht spürbar etwas. Außerdem interessiert mich der Ansatz über die Kettenbruchzerlegung jetzt. Hier zieht Gewitter auf, also die beste Gelegenheit für mich, noch einmal mit Stift und Papier das Ganze anzugehen.
:
Bearbeitet durch User
Walter T. schrieb: > Für Z = 40973 und N = 29147 [...] Die ersten Glieder der Entwicklung von 40973/29147 in einen regulären Kettenbrauch lauten [1;2,2,6,1,1,2,1,12,1,1,...]; zum Weiterrechnen hatte ich keine Lust mehr. > Mit vollständiger Enumeration komme ich auf > z = 9067, n = 6450. Das ist in der Tat der 11. Näherungsbruch; er ergibt sich genau aus der oben angegebenen Teilfolge. > Auffällig an dem Beispiel ist, dass Zähler und Nenner > recht klein sind. Das haben Kettenbruch-Näherungen so an sich. Die Näherung 355/113 für Pi stimmt auf sieben geltende Ziffern.
Walter T. schrieb: > Ich habe dann eine vorher nicht bestimmbare Anzahl an Quotienten q_0 bis > q_n und zwei Reste r_n und r_n+1. Wenn ich weiter drüber nachdenke: Dass ich die Ordnung des Kettenbruchs nicht a priori absehen kann, ist ja überhaupt kein Problem. Der Euklid-Algorithmus braucht ja nicht lange. Da ist das gleiche Problem bei jedem sprintf() schlimmer.
:
Bearbeitet durch User
Weiß nicht, ob schon genant wurde, wie wärs mit Shiften? Also Zähler und Nenner so lange nach links shiften bis das MSB entweder des Zählers oder Nenners 1 ist. Dann die jeweiligen höherwertigen 16bit kopieren, das sollte die beste Näherung sein. Will man noch den kleinstmöglichen Zähler und Nenner dann nochmal beide nach rechts shiften bis eine 1 im LSB steht. Shiften ist ja eine Multiplikation (Division) mit 2. Zähler und Nenner gleichzeitig shiften kürzt sich weg, ist also eine Erweiterung des Bruchs. Von der Rechenzeit käme man mit max 16 Linksshifts und anschließend max 16 Rechtsshifts hin.
Thorsten M. schrieb: > Weiß nicht, ob schon genant wurde, wie wärs mit Shiften? Walter T. schrieb: > Erster naiver Ansatz: n = INT16_MAX; aber es lässt sich für viele Brüche > Z/N zeigen, dass es bessere Approximationen gibt. Z = 40973 und N = 29147 ist die oben genannte Näherung z.B. besser als 10^-8.
:
Bearbeitet durch User
Walter T. schrieb: > Wenn ich weiter drüber nachdenke: Dass ich die Ordnung > des Kettenbruchs nicht a priori absehen kann, ist ja > überhaupt kein Problem. Der Euklid-Algorithmus braucht > ja nicht lange. Soweit ich weiss, ist die reelle Zahl mit der am langsamsten konvergierenden Kettenbruchentwicklung der Goldene Schnitt. Dessen Entwicklung lautet [1;1,1,1,1,1....]. Für eine vorgegebene Genauigkeit braucht jede andere Zahl somit höchstens gleich viele Schritte. Zu allem Überfluss sind Zähler und Nenner dieser Entwicklung aufeinanderfolgende Elemente der Fibonacci-Folge, und auffälligerweise ist gerade das 25. Element dieser Folge das erste, das größer als 2^16 ist.
Nachtrag: Der Ansatz über den Kettenbruch ist goldrichtig. Der angehängte Quelltext ist alles andere als optimiert, aber er schafft das Zehnfache von dem, was oben mit vollständiger Enumeration in 28 Sekunden gemacht wurde in einer Zeit, die ich nicht mit der Stoppuhr erfassen kann. Er liefert insbesondere auch in allen getesteten Fällen das gleiche Ergebnis wie die vollständige Enumeration. Wahrscheinlich ist noch der eine oder andere Bug drin, aber den bekommt man noch plattgebügelt. Insbesondere wird es vermutlich sinnvoll sein, den Stack, den er sich genehmigen darf, zu begrenzen. Danke nochmal insbesondere an Yalu für den richtigen Tipp und danke an die anderen für die ebenfalls durchgängig brauchbaren Beiträge!
:
Bearbeitet durch User
Walter T. schrieb: > Für Z = 40973 und N = 29147 kommen z = -24563 und n = 29147 heraus. Ich habe vergessen, auch den Zähler in die Abbruchbedingung mit aufzunehmen. Der Algorithmus liefert deswegen 40973/29147 als beste Näherung. Du hast dann wohl die 40973 in ein int16_t konvertiert, was wegen des Überlaufs -24563 ergibt. Ich muss mal schauen, wie ich das korrigieren kann (aber heute nicht mehr). Die Abbruchbedingung selber ist nicht das Problem, aber bei der Bestimmung der besten Nebennäherung kann es passieren, dass der Zähler trotzdem größer als das Limit wird. > Mit vollständiger Enumeration komme ich auf z = 9067, n = 6450. > Auffällig an dem Beispiel ist, dass Zähler und Nenner recht klein > sind. Dein Algorithmus bestimmt das, was hier als "beste Näherung 2. Art" bezeichnet wird: https://de.wikipedia.org/wiki/Kettenbruch#Zwei_M%C3%B6glichkeiten_bester_N%C3%A4herung Dabei wird für die Bewertung der Lösungskandidaten nicht – wie bei der besten Näherung 1. Art – der absolute Fehler, sondern das Produkt aus absolutem Fehler und dem Nenner des Kandidaten herangezogen. Dadurch werden Näherungen mit kleinem Nenner deutlich bevorzugt. > Außerdem interessiert mich der Ansatz über die Kettenbruchzerlegung > jetzt. Hier zieht Gewitter auf, also die beste Gelegenheit für mich, > noch einmal mit Stift und Papier das Ganze anzugehen. Der Trick bei der Sache ist es, den endlichen Kettenbruch nicht als Verkettung nichtlinearer Funktionen f auf ℚ mit f(x) = q_i + 1/x, sondern als Verkettung linearer Funktionen auf ℕ×ℕ mit g((z, n)) = (q_i·z + n, z) aufzufassen. Solche Funktionen können als Matrix dargestellt werden, wodurch aus der Verkettung der Funktionen ein leichter handzuhabendes Produkt aus 2×2-Matrizen wird: https://de.wikipedia.org/wiki/Kettenbruch#Matrixdarstellung Dies ermöglicht es, den Wert von [q_0;q_1...q_(n+1)] rekursiv aus dem Wert von [q_0;q_1...q_(n)] und q_(n+1) zu berechnen. Damit hat man mit jedem q_i, das der Euklidische Algorithmus generiert, sofort auch den Zähler und Nenner des bis zu diesem q_i ausgewerteten Kettenbruchs. Ohne diesen Trick muss man alle Koeffizienten in einer Liste speichern und sich für die Berechnung des Kettenbruchs jedesmal in einer Schleife vom letzten bis zum ersten Koeffizienten durchhangeln. Das geht natürlich auch, braucht aber mehr Rechenzeit und ist umständlicher zu programmieren.
:
Bearbeitet durch Moderator
Yalu X. schrieb: > Dabei wird für die Bewertung der Lösungskandidaten nicht – wie bei der > besten Näherung 1. Art – der absolute Fehler, sondern das Produkt aus > absolutem Fehler und dem Nenner des Kandidaten herangezogen. Dadurch > werden Näherungen mit kleinem Nenner deutlich bevorzugt. Stimmt. Gestern sah das noch nach der geschicktesten Wahl aus. Aber ich will ja eigentlich den relativen Fehler einer Operation A*z/n minimieren, nicht den relativen Fehler z/n. Dafür muss ich natürlich den absoluten Fehler von z/n minimieren. Yalu X. schrieb: > Der Trick bei der Sache ist es, den endlichen Kettenbruch nicht als > Verkettung nichtlinearer Funktionen f auf ℚ mit f(x) = q_i + 1/x, > sondern als Verkettung linearer Funktionen auf ℕ×ℕ mit g((z, n)) = > (q_i·z + n, z) aufzufassen. Solche Funktionen können als Matrix > dargestellt werden, wodurch aus der Verkettung der Funktionen ein > leichter handzuhabendes Produkt aus 2×2-Matrizen wird: > > https://de.wikipedia.org/wiki/Kettenbruch#Matrixdarstellung > > Dies ermöglicht es, den Wert von [q_0;q_1...q_(n+1)] rekursiv aus dem > Wert von [q_0;q_1...q_(n)] und q_(n+1) zu berechnen. Endlich mal jemand, der es so erklärt, dass ich das auch verstehe. Scherz beiseite: Das war jetzt wirklich die richtige Erklärung zum richtigen Zeitpunkt. Gestern habe ich die Matrixdarstellung wegen der schieren Menge an Neuem als "exotischer Nebenpfad" abgetan. Yalu X. schrieb: > Ohne diesen Trick muss man alle Koeffizienten in einer Liste speichern > und [...] Was ich noch nicht ergründen konnte: Der Ansatz besteht darin, beim "Zurückgewinnen" des ursprünglichen Bruchs die Koeffizientenliste irgendwann abzubrechen. (Oder besser: Später anzufangen, wenn die Liste rückwärts wieder aufgedröselt wird). Das entspricht ja, ein Restglied Null zu setzen. Bei anderen Approximationen kann es ein besseres Ergebnis liefern, ein Restglied auf 1 zu setzen. Habe ich das richtig verstanden, dass ein frühzeitiger Abbruch immer ein tendenziell zu großes Ergebnis liefert (nach dem 0-ten Glied), weil der Nenner immer schwerer wird? Edit: Nee, das ist Blödsinn. Der Nenner wird abwechselnd schwerer und leichter. Es wird ja ständig der Kehrwert gebildet. Das dauert noch, bis ich zu dem Konstrukt Intuition entwickele.
:
Bearbeitet durch User
Semi-OT: Kennt jemand von euch ein gutes erstsemestertaugliches Mathematik-Lehrbuch, in dem dieses und ähnliche Themengebiete behandelt werden? Mein erstes Semester ist zwar sehr lange her, aber dieser Themenkreis wurde absolut überhaupt nicht angeschnitten. (Es gab letztens einen passenden XKCD dazu: https://xkcd.com/2501/ )
:
Bearbeitet durch User
Der Ansatz ist richtig, koennte mit etwas mehr Mathe abgekuerzt werden. Es gibt verschiedene Bezeichnung, verschiedene Ansaetze. Mathematische Methoden der Physik, Mathematik fuer Informatiker, usw. Benoetigen aber eine Aufbau. Ich wuerd mich erst mal mit dem ersten Ansatz, den Teilen durch 2^n, bedeutet Schieben, zufrieden geben. Und mir ueberlegen, weshalb ich mehr Aufloesung und Genauigkeit benoetige. Wieviele Bit hat mein ADC, welche Genauigkeit hat er ? Regelungen rechne ich zB nie in zB Grad Celsius, sondern in ADC Einheiten. Ich lasse auf ADC Endwert regeln, micht auf Grad Celsius. Alternativ mit mehr Stellen rechnen. Wenn die Rechenzeit zu lange dauert, zB in einem Loop die periodischen Aufgaben zu stark verzoegert, die Rechnung in einer Zustandsmaschine, zB ein Digit pro Ausfuehrung rechnen. Das kann man machen, um Anzeigegroessen, welche hoechtens 3 Mal pro Sekunge beoetigt werden, zu rechnen, wenn der Loop schneller als 10ms sein muss, und die Rechnung 30ms dauert.
Pandur S. schrieb: > Ich wuerd mich erst mal mit dem ersten Ansatz, den Teilen durch 2^n, > bedeutet Schieben, zufrieden geben. Das ist okay. Kannst Du so machen. Ich bin gerade in die komplette Gegenrichtung unterwegs. Ich bewege mich von einer Genauigkeitsdiskussion in jedem Einzelschritt hin zu einer überschaubaren Anzahl von Operationen mit definierter Genauigkeit und bekannter Geschwindigkeit. Viel Quelltext kann man dadurch gar nicht mal löschen, aber viele Zeilen Kommentar und viele Assertions. Das ist insbesondere sehr praktisch, weil das sehr anstrengender Kommentar ist - und leider auch nicht sehr nachhaltig. Immer wenn die Reihenfolge in der Bearbeitungskette geändert wird, muss alles angepasst werden. Aber lassen wir die Motivation außen vor. Mit der Implementierung bin ich ja schon in trockenen Tüchern. Es gibt keinen Grund, auf eine schlechtere zu wechseln. Nur noch auf eine bessere. Außerdem ist dieser Abstecher in die Zahlentheorie schon für sich interessant. Selbst wenn ich keinen Takt gewonnen hätte, hätte sich das gelohnt. Selbst wenn sich morgen herausstellte, dass es ein __builtin_reduce_fraction() gibt, das alles in sieben Takten erledigt, hätte sich das gelohnt.
:
Bearbeitet durch User
Walter T. schrieb: > Kennt jemand von euch ein gutes erstsemestertaugliches > Mathematik-Lehrbuch, in dem dieses und ähnliche Themengebiete behandelt > werden? Die ersten beiden Bücher aus meinem Regal, die ich dazu gefunden habe sind: Karl Strubecker, Einführung in die Höhere Mathematik, Band I., Oldenbourg Verlag, 1966 27. Kettenbrüche S. 77 28. Anwendungen S. 81 29. Unendliche Kettenbrüche S. 85 30. Periodische Kettenbrüche S. 88 und Harald Scheid, Zahlentheorie, BI-Wissenschaftsverlag, 1994 1.8 Kettenbrüche S. 46 1.9 Periodische Kettenbrüche S. 56 Nachtrag: Neben einer Quelle von 1966 habe ich auch etwas moderneres: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfINTRO.html
:
Bearbeitet durch User
Alexander S. schrieb: > Karl Strubecker, Einführung in die Höhere Mathematik, Band I., Alexander S. schrieb: > Harald Scheid, Zahlentheorie, BI-Wissenschaftsverlag, 1994 Bei beiden sieht das Inhaltsverzeichnis brauchbar aus, bei beiden kann ich wahrscheinlich im Laufe der übernächsten Woche einen Blick hineinwerfen. Danke für die beiden Tipps!
Hier noch eine dritte Quelle: Mangoldt, Knopp, Höhere Mathematik 1, Hirzel Verlag, 1990 64. Endliche regelmäßige Kettenbrüche S. 144 65. Näherungsbrüche S. 147 66. Beispiele S. 149
Man sollte auch berücksichtigen, daß viele 32Bitter keine HW-Division können oder die Division mehr Takte benötigt als die Multiplikation. Es kann daher gut sein, daß eine float Multiplikation mit dem Kehrwert sogar schneller ist als die Ganzzahl Division bzw. kaum langsamer. Der ganze Aufwand kann also umsonst sein. Ich habe viele Regelkreise, die einen großen Dynamikbereich benötigen, z.B. eine Elektronenquelle für 10nA..1mA. Da würde ich mir einen abbrechen, wenn ich auf float verzichten wollte. Die Teilchenquellen werden über den Filamentstrom geregelt, d.h. die Regelung muß eh träge sein, damit sie nicht schwingt (dominanter Pol).
Peter D. schrieb: > Ich habe viele Regelkreise, die einen großen Dynamikbereich benötigen, In einem Regelkreis hast Du einen Feedback-Zweig. In einem Kreis mit Zustandsrückführung können sich Diskretisierungsfehler nicht akkumulieren. Da ist float perfekt. Das Gegenteil ist z.B. eine Streckenmessung über Pulszählung. Da läufst Du mit float irgendwann in eine Sättigung und es gilt z.B. 16777216 + 1 + 5 != 16777216 + 5 + 1. Ich stelle mir das übrigens absolut brutal vor, soetwas zu debuggen, wenn man das nicht vorher weiß. Zumal bei vielen Längeneinheiten es ja durchaus ein wenig dauert, bis man bei solchen Zahlen angelangt ist. (Eintrag im Bugtracker: "Wenn man sehr langsam fährt, zählt er nicht mehr hoch! Tritt alle vier Wochen auf!") Dass float für vieles gut ist heisst nicht, dass es für alles gut ist. Aber wir sind hier ja eh im Off-Topic-Forum. Hier dürfen auch Zahlenspielereien rein, denen jegliche praktische Anwendung fehlt. Lassen wir die Anwendung beiseite. Das Problem an sich ist interessant genug. Edit: Bevor jemand Unbedarftes (was ich keinem Mitdiskutanten unterstelle, aber man stößt ja auch beim Googlen auf Threads) beim Lesen das obige Beispiel falsch versteht: Das ist kein Epsilon-Problem beim Vergleich. Es kommen immer ganze Zahlen heraus. Nur eben unterschiedliche je nach Operations-Reihenfolge.
:
Bearbeitet durch User
Beitrag #6816523 wurde vom Autor gelöscht.
Ich habe oben etwas falsch korrigiert und nun ist meine Zeit abgelaufen. (Der Zeilenumbruch macht mich kirre!) Gemeint ist: "Die Ausdrücke 16777216 + (5 + 1) und 16777216 + 5 + 1 liefern unterschiedliche Werte mit 32-Bit-Float." Zurück zum Thema: Habe eben in der Badewanne noch einmal die Neben-Näherungsbrüche angeschaut. Mit einem Tag Abstand ist das doch gar nicht so kompliziert. Ich versuche das erst einmal selbst - also bitte nicht vor Montag vorsagen, Yalu! Edit: Hat sich erledigt. Wenn man kein Problem damit hat, jeweils zwei Brüche zwischenzuspeichern, ist das wirklich geradeheraus. Danke für das Stichwort! Ohne wäre ich nie darauf gekommen. An der Genauigkeit macht das nicht viel. Ich habe tatsächlich gerade noch kein Beispiel gefunden, wo es bei der anschließenden Multiplikation mit einem großen 64-Bit-Integer eine komplette Stelle Unterschied macht. Außer bei einem Beispiel, wo der Wert des Bruchs sehr groß ist und der Nebenbruch einfach den größeren Zähler hat, bevor abgebrochen wird. Aber es ist schön, es probiert zu haben und es klappt. Quelltext kommt, sobald ich ihn schön finde. Edit2: Kann man sich auf die Eigenschaft verlassen, dass die Hauptbrüche immer abwechselnd über und unter dem realen Wert sind? Edit3: Klar, muss ich ja. Sonst wären die Nebenbrüche nicht dichter dran. Edit4: Willkommen in meiner Lerngruppe!
:
Bearbeitet durch User
Yalu X. schrieb: > Ich habe vergessen, auch den Zähler in die Abbruchbedingung mit > aufzunehmen. Das habe ich jetzt nachgeholt. Außerdem habe ich den Vergleich der Fehler der am Ende des Algorithmus entstehenden beiden Lösungskandidaten von double auf uint64_t umgestellt, da ich befürchte, dass die Auflösung von double (52 Bit) in einigen Fällen nicht ausreichend ist. Ich müsste dafür zwar noch ein Beispiel konstruieren, wo dies relevant wird, aber mit der neuen Methode ist man auf jeden Fall auf der sicheren Seite. Schließlich habe ich noch einen Wrapper für vorzeichenbehaftete Brüche hinzugefügt. Übrigens solltest du (falls du es noch nicht getan hast) in deinem approx2.c in Zeile 79
1 | for( size_t ii = 1; ii<nEl; ii++ ) |
das < durch ein <= ersetzen, sonst wird in vielen Fällen nicht die beste, sondern nur die zweitbeste Näherung gefunden. Könntest du vielleicht noch etwas dazu sagen, wozu du die rationale Näherung brauchst? Du schriebst oben zwar etwas von Pulszählung, Streckenmessung und akkumulierenden Fehlern. Aber so ganz verstehe ich den Zusammenhang mit der rationale Näherung nicht. Einige hier vermuten ja, dass du damit einfach nur Zahlenwerte skalieren möchtest, und da wäre die FP-Multiplikation auf dem STM32F446 ganz klar schneller als die Integer-Multiplikation und -Division. Aber es gibt natürlich auch Fälle, wo die FP-Arithmetik überhaupt nicht weiterhilft, bspw. bei der Parametrierung eines Frequenzteiles mit rationalem Teilungsfaktor. Walter T. schrieb: > Edit2: Kann man sich auf die Eigenschaft verlassen, dass die Hauptbrüche > immer abwechselnd über und unter dem realen Wert sind? Bei der Sorte von Kettenbrüchen, um die es hier geht (also mit ausschließlich positiven Koeffizienten), ja.
Guten Morgen, danke, dass Du Deine Verfeinerung mit uns teilst! Sie ist auf jeden Fall schon einmal schneller als meine. Ganz habe ich sie noch nicht verstanden. Aber das ist etwas für heute abend. Ich hatte noch keinen Kaffee. Etwas Off-Topic:
1 | |
2 | if (zv < 0) { |
3 | negative = true; |
4 | zv = -(uint32_t)zv; |
5 | }
|
Ist das erlaubt?
Bezueglich float und integer. Ma sollte sich vergewaertigen, dass Int32 einen dynamischen Bereich von 9 digits bringt, waehrend es bei float32 nur 6 digits sind. Ich mache daher meine Regelungen welchen auf 24 Bit Wandlern beruhen auf Int32, mit float32 haette ich schon zu Beginn weg verloren. float32 hat nur 24bit Mantisse.
Walter T. schrieb: > if (zv < 0) { > negative = true; > zv = -(uint32_t)zv; > } > Ist das erlaubt? Es ist nicht nur erlaubt, sondern auch unabhängig von der internen Darstellung von Integer-Zahlen und damit portabel. Die Konvertierung einer negativen Zahl in einen Unsigned-Typ ist in Ordnung: "6.3.1.3 Signed and unsigned integers When a value with integer type is converted to another integer type other than _Bool, if the value can be represented by the new type, it is unchanged. Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type." Der Vorzeichenwechsel mit dem "-"-Operator ist ebenfalls in Ordnung: 6.2.5 Types ... A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type." Wichtig ist, dass zuerst in unsigned konvertiert und dann erst das Vorzeichen geändert wird. Andersherum führt -zv für zv=INT32_MIN zu undefined Behavior: "5.5 Expressions ... If an exceptional condition occurs during the evaluation of an expression (that is, if the result is not mathematically defined or not in the range of representable values for its type), the behavior is undefined."
Egon D. schrieb: > Die ersten Glieder der Entwicklung von 40973/29147 > in einen regulären Kettenbrauch lauten > [1;2,2,6,1,1,2,1,12,1,1,...]; zum Weiterrechnen > hatte ich keine Lust mehr. Du warst fast fertig :-) 40973/29147 = [1;2,2,6,1,1,2,1,12,1,1,4] http://www.arndt-bruenner.de/mathe/scripts/bruchrechnung1.htm#kettenbruch
Yalu X. schrieb: > Es ist nicht nur erlaubt, sondern auch unabhängig von der internen > Darstellung von Integer-Zahlen und damit portabel. Gut zu wissen. Das Idiom kannte ich noch nicht, aber spart einen Vergleich (für den Sonderfall INT_MIN) gegenüber meinem bisherigen Vorgehen. Yalu X. schrieb: > Übrigens solltest du (falls du es noch nicht getan hast) in deinem > approx2.c in Zeile 79 > for( size_t ii = 1; ii<nEl; ii++ ) > > das < durch ein <= ersetzen, sonst wird in vielen Fällen nicht die > beste, sondern nur die zweitbeste Näherung gefunden. Hoppla, da hatte ich wohl einen Zaunpfahl vor dem Kopf. Ich hätte von 2 bis nEl testen sollen. Pandur S. schrieb: > Ich mache daher meine Regelungen welchen auf 24 Bit Wandlern beruhen auf Int32 Um den Dynamikbereich beneiden Dich viele. Dann schwäche ich meine obige Aussage und füge das Wort "oft" hinzu. -- Was mir noch etwas Kopfzerbrechen bereitet: Als "historische" Begründung für die Kettenbruchentwicklung wird das Bestreben Huygens angeführt, den Bruch 77708431/2640858 (Verhältnis der Umlaufbahnen von Erde und Saturn) durch das praktikablere Teilungsverhältnis 206/7 zu approximieren. Das Problem: Nur ein absolut Wahnsinniger würde ohne Not ein Zähnezahlenverhältnis von 412/14 als einstufiges Getriebe realisieren, zumal sich Erde und Saturn ja im gleichen Umlaufsinn bewegen. Kettenbrüche zu erfinden, um ein Planetarium zu bauen, lasse ich mal nicht als Indiz für den Wahnsinn gelten. Also brauchte er mindestens ein zweistufiges Getriebe. Aber das würde bedeuten, dass er in Wirklichkeit noch einen Freiheitsgrad hatte, um die Genauigkeit zu steigern:
:
Bearbeitet durch User
Yalu X. schrieb: > Walter T. schrieb: >> if (zv < 0) { >> negative = true; >> zv = -(uint32_t)zv; >> } >> Ist das erlaubt? > > Es ist nicht nur erlaubt, sondern auch unabhängig von der internen > Darstellung von Integer-Zahlen und damit portabel. Hier ist zv wohl int32_t. Und dann ist zwar -(uint32_t)zv zulässig, aber die anschliessende Zuweisung an int32_t wird im Fall von INT32_MIN interessant. Denn das ist zunächst eine positive Zahl ausserhalb des zulässigen Wertebereichs von zv.
1 | uint32_t u_zv = zv; |
2 | if (zv < 0) { |
3 | negative = true; |
4 | u_zv = -(uint32_t)zv; |
5 | }
|
:
Bearbeitet durch User
(prx) A. K. schrieb: > aber > die anschliessende Zuweisung an int32_t wird im Fall von INT32_MIN > interessant. Danke für den Hinweis und die Korrektur. Ich habe mich wohl zu sehr darauf konzentriert, die rechte Seite der Zuweisung richtig zu machen, so dass ich ganz vergessen habe, dass auf der linken Seite noch der falsche Typ steht. Die korrigierte Version des Programms habe ich angehängt.
Walter T. schrieb: > Das Gegenteil ist z.B. eine Streckenmessung über Pulszählung. Da läufst > Du mit float irgendwann in eine Sättigung Pulse zählt man natürlich immer als Ganzahl und nicht als float. Und ganz zum Schluß zur Anzeige rechnet man erst in die jeweilige Maßeinheit um. Da kann man dann auch nationale Vorlieben berücksichtigen.
Peter D. schrieb: > Walter T. schrieb: >> Das Gegenteil ist z.B. eine Streckenmessung über Pulszählung. Da läufst >> Du mit float irgendwann in eine Sättigung > > Pulse zählt man natürlich immer als Ganzahl und nicht als float. Und > ganz zum Schluß zur Anzeige rechnet man erst in die jeweilige Maßeinheit > um. Da kann man dann auch nationale Vorlieben berücksichtigen. Meine Rede. Und wenn Du jetzt noch der Meinung bist, dass sich ein 64-Bit-Integer mit einer rationalen Zahl viel komplikationsärmer als mit einem float umrechnen lässt, sind wir auf einem gemeinsamen Nenner.
Allenfalls kann man sich den Bresenham Algorithmus ueberlegen. Vom Punkt (Z,N) nach (0,0) eine Linie ziehen, und schauen, wo sie am naechsten an anderen Punkten vorbei geht.
:
Bearbeitet durch User
Jetzt bin ich mal dazu gekommen, approx3a.c detailliert durchzugehen. Schade. Ich sehe kein Verbesserungspotenzial. Vielleicht bis auf die Winzigkeit, dass ich mir noch q != 0 als Rückgabewert gegönnt habe. Wenn ich nicht absolut daneben liege, lässt sich so ja direkt ohne Mehraufwand unterscheiden, ob der Bruch approximiert oder nur reduziert wurde. (Wieso ist jetzt eigentlich der Cast im Wrapper weg? Ich dachte immer, signed integer overflow und damit -INT_MIN sei undefined behaviour.) Ich habe das gerade mal versucht, auf 64-Bit-Integer zu bekommen, und der Vergleich am Schluß benötigt fast die gleiche Rechenzeit wie die Hauptaufgabe. :-)
Thread beobachten
Seitenaufteilung abschaltenBitte 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.