Gesucht: Nächste rationale Zahl mit Nebenbedingung |
14.02.2023, 18:38 | GMath | Auf diesen Beitrag antworten » | |||||||
Gesucht: Nächste rationale Zahl mit Nebenbedingung Ich bin neulich über die Aufgabe gestolpert, zu einer gegebenen rationalen Zahl (r/s, r und s teilerfremd) diejenige/ diejenigen (t/u) zu finden, die ihr am nähesten ist, und bei denen entweder Zähler oder Nenner kleiner als jew. r und s sind. Kann man das direkt aus r und s ableiten, oder bleibt einem nichts anderes übrig als die Nähe der Geraden r/s zu testen? Beispiel 1000 / 799 Gesucht Bruch mit jew. Zähler und Nenner kleiner 1000. Intuitiv hätte ich erwartet, dass das der Bruch sein wird, dessen Zähler so gerade eben die Nebenbedingung erfüllt, d.h. 999 / 798 o.ä. Oder als Ableitung von der Dezimaldarstellung (1,1215645...) Aber falsch gedacht. Der optimale Bruch ist 801 / 640. (Ursprung des Problems: Umrechnung der Seitenverhältnisse beim Beschneiden von Frames; für den Fall, dass die exakten Werte zu groß für die Eingabefelder der Filmbearbeitunsapp. sind). |
|||||||||
14.02.2023, 19:10 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Naja Fakt ist, dass für positive Nenner auf jeden Fall gilt Wenn teilerfremd sind, dann wird man keine mit finden, so dass ist. Das beste, was man finden kann ist , Nun ergibt der EEA für die Werte . D.h. einer der beiden Brüche oder ist dann das gesuchte : Gemäß (*) natürlich der mit dem größeren Nenner . ![]() |
|||||||||
14.02.2023, 20:20 | GMath | Auf diesen Beitrag antworten » | |||||||
Vielen Dank für Deine Antwort! Man braucht wohl etwas Übung, um darauf zu kommen. Unklar ist mir jedoch, wie Du mit dem EEA auf 801/640 kommst - bei mir liefert er mit 1000 und 799 immer nur 199/159. |
|||||||||
14.02.2023, 20:48 | GMath | Auf diesen Beitrag antworten » | |||||||
Obigen Beitrag löschen geht nicht mehr. Dann muss ich also zu meiner Schande stehen lassen, wie ich die einfache Umformung nicht gesehen habe. ![]() |
|||||||||
14.02.2023, 20:56 | IfindU | Auf diesen Beitrag antworten » | |||||||
Damit niemand über den Beitrag stolpert, sich genauso wundert und dann wütend auf GMath ist, weil er keine Erklärung gepostet hat, hole ich das kurz nach ![]() Trivialerweise gilt dank der Kommutativität der reellen Zahlene für alle . Damit wird trivialerweise von und für alle erfüllt und damit gilt . In HALs Fall dann eben . |
|||||||||
14.02.2023, 21:18 | GMath | Auf diesen Beitrag antworten » | |||||||
Na-ja, ich habe deswegen keine Erklärung gepostet, weil ich den Eindruck hatte, dass nur ich diese Umformung nicht auf Anhieb verstanden habe. ![]() Nachdem ich das jetzt soweit durchdrungen habe, ist mir klar geworden, dass mein Problem damit doch noch nicht richtig gelöst ist. Tatsächlich gibt es in meinem ersten Post ja einen Unterschied zwischen der Formulierung des Problems und am Ende dessen Herkunft: Weil eigentlich sollen die gesuchten t und u nicht nur jeweils kleiner als r und s sein, sondern sie sollen kleiner als eine jeweils vorgegebene Grenze sein (von wegen Stelligkeit der Eingabemaske). Geht das mit einer Abwandlung, oder dann doch nur mit Dumm-Suche der r/s-Gerade? |
|||||||||
Anzeige | |||||||||
|
|||||||||
14.02.2023, 22:08 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Nun, man kann das Verfahren ja modifizieren: Findet man keine passenden Zahlen mit , dann vielleicht mit =2 oder =3, ... Die alle basieren auf der schon ermittelten EEA-Lösung, und erfüllen dann mit etwas Probieren irgendwann die Forderungen: Übrigens: Die Kettenbruch-Näherungsbrüche des Ausgangsbruchs sind schon mal gute Wegmarken: Denn für jeden solchen Näherungsbruch gilt für alle mit . Tatsächlich gilt sogar noch mehr, nämlich . Für sind das , , und , und dann ist man bereits bei , also der Ausgangszahl selbst. |
|||||||||
15.02.2023, 00:22 | Finn_ | Auf diesen Beitrag antworten » | |||||||
Binäre Suche im Stern-Brocot-Baum
|
|||||||||
15.02.2023, 11:19 | GMath | Auf diesen Beitrag antworten » | |||||||
Verstehe ich das richtig: Das Verfahren "springt" in seinen Iterationen (ähnlich wie die von HAL 9000 vorgeschlagene Modifikation) und findet dadurch i.allg. nicht das Optimum in einem einschränkenden Rechteck? |
|||||||||
15.02.2023, 12:41 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Nun, deutlich eleganter als mein Vorschlag: Es wird da eine Eigenschaft des Stern-Brocot-Baums genutzt, die dafür sorgt, dass all die von dir gesuchten Näherungsbrüche als Intervallenden der Stern-Brocot-Näherungsintervalle auftauchen (die Umkehrung gilt nicht, weswegen Finn in Zeile 14 noch die Abfrage eingefügt hat).
So wie ich das verstehe, findet das Pythonscript ALLE Näherungsbrüche in genau dem von dir beschriebenem Sinne. Probier es aus! |
|||||||||
15.02.2023, 16:02 | GMath | Auf diesen Beitrag antworten » | |||||||
Da mein PC nicht Python kann, und ich im wesentlichen nur C/C++ habe ich's online laufen lassen. Die Ausgabe: 1/1 3/2 4/3 5/4 104/83 109/87 114/91 119/95 124/99 129/103 134/107 139/111 144/115 149/119 154/123 159/127 164/131 169/135 174/139 179/143 184/147 189/151 194/155 199/159 602/481 801/640 1000/799 Ich brauche ja nur das Ergebnis, und nicht den Weg, d.h. 801/640. Und dann gibt's ja noch die Nebenbedingung (Ergebnis in einem vorgegebenem Rechteck Z/N). Ich vermute mal per Ersetzung der Zeile 17 durch irgendwie: if not inRectangle (m, (Z,N)): break Oder? |
|||||||||
15.02.2023, 16:17 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Du kannst natürlich das Skript nach deinem Gusto so umgestalten, dass je nach vorgegebenem Fenster nur der dazu passende beste Näherungsbruch ausgegeben wird, statt wie hier die Liste aller Näherungsbrüche. Dazu wird man sicher einen wie von dir vorgeschlagenen Abbruch vornehmen (aber wohl schon zwischen Zeile 13 und 14), außerdem das "yield m" entfernen und stattdessen am Prozedurende ein "return best" ergänzen. P.S.: Langsam mutiert das zur Programmieraufgabe. |
|||||||||
15.02.2023, 17:23 | GMath | Auf diesen Beitrag antworten » | |||||||
Der Programmcode war ja kommentarlos gepostet worden, also war es notwendig, ihn zu verstehen, sowie die für die Nebenbedingung erforderliche Modifikation. Tatsächlich war mir bis gerade nicht klar, ob der Ablauf der Traversierung nicht vielleicht wegen der Nebenbedingung (Z,N) Werte "übersieht". Auch das ein Grund, mich der prinzipiellen Korrektheit der Modifikation zu vergewissern. Jedenfalls glaube ich erkannt zu haben, dass es korrekt ist. ES SEI DENN... man bräuchte das einschränkende Rechteck irgendwo (und nicht ab dem Ursprung). D.h. auch noch Mindestwerte für (t,u). (Ggf. interessant, aber bei meinem Szenario nicht der Fall ![]() Die obige spezielle Traversierung des Stern-Brocot-Baums ist offenbar ein sehr guter (wenn nicht optimaler) Algorithmus zur Bestimmung der Lösung. Vielen Dank allen Beteiligten! |
|||||||||
15.02.2023, 17:49 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Wirklich? Eine Stellschraube bleibt dir da ja auch noch: Es steht nichts davon oben, dass auch t,u teilerfremd sein sollen. Also beide mit einem Faktor >1 multiplizieren schiebt ein "zu kleines" Paar womöglich doch ins Fenster. ![]() |
|||||||||
15.02.2023, 18:39 | Finn_ | Auf diesen Beitrag antworten » | |||||||
Portierung auf C89
|
|||||||||
15.02.2023, 20:06 | GMath | Auf diesen Beitrag antworten » | |||||||
Nuitka? ==> "Der Wodka ist gut, aber das Steak ist lausig" |
|||||||||
15.02.2023, 21:13 | Finn_ | Auf diesen Beitrag antworten » | |||||||
Charmantes Programm. Ich mutmaße allerdings mal, der Adressat des von Nuitka erzeugten Programmtextes soll nicht vorrangig der menschliche Leser sein. |
|||||||||
16.02.2023, 08:41 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Es ist sicher auch keine komplette Umsetzung des Python-Codes, zumindest wenn man den für SEHR große Integerzahlen nutzen will: Ich kenne keine C-Implementierung, wo Datentyp "int" Zahlen mit mehr als 64 Bit erfassen kann (die Regel ist aktuell eher 32 Bit), während Pythons Integer-Zahlen ja nahezu beliebig groß werden können (natürlich durch Laufzeit und Speicherplatz gibt es eine gewisse Begrenzung). Dazu müsste man schon Spezialbibliotheken einbinden (wie z.B. die gmp). |
|||||||||
01.03.2023, 20:43 | GMath | Auf diesen Beitrag antworten » | |||||||
... wobei die Zahlen gar nicht mal so "SEHR groß" zu sein brauchen, damit es mit C so nicht mehr geht: Ab 1e4/(1e4-1) mit 32 bit signed ist schon Schluss. Allerdings ist mein ad-hoc-Algorithmus (die Steigungsgerade per double hochhangeln) noch numerisch-instabiler - da führt die Stellenauslöschung schon ab 1e3/(1e3-1) zu falschen Ergebnissen. Was tun? Breiteres Datenformat, oder ein modifizierter oder anderer Algorithmus, der nicht so numerisch-instabil bzw. speicherhungrig ist? (Aber - wie schon angemerkt - das ist ja kein mathematisches Problem, sondern des Algorithmus bzw. Implementation). |
|||||||||
01.03.2023, 22:50 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Versteh ich nicht - womit ist ab 10000/9999 "Schluss" im Zusammenhang mit 32Bit-Integerzahlen? ![]() |
|||||||||
01.03.2023, 23:13 | GMath | Auf diesen Beitrag antworten » | |||||||
Wenn Du die C-Portierung der Stern-Brocot-Traversierung von hier laufen lässt (bspw. hier), dann ist (spätestens ab r/s=10000/9999) die generierte Ausgabereihe unvollständig. Vergleich bspw. mit der entsprechenden Ausgabereihe des Python-Programms. ==> Schon bei 1000 braucht man 64bit. |
|||||||||
02.03.2023, 07:41 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Ah, Ok: Die Distanzbestimmung ist das Problem. Die Verzweigung gemäß Stern-Brocot sollte an sich mit kleiner als klappen, aber dieses
|
|||||||||
02.03.2023, 09:20 | GMath | Auf diesen Beitrag antworten » | |||||||
Ja. Ich wollte darauf hinweisen, dass der Algorithmus nicht erst bei sehr großen Zahlen, sondern eben schon bei erschreckend kleinen Zahlen ("erschreckend kleine Zahlen"? ... "phobia parvi numeri"?) zu gemeinen Überläufen/ Stellenauslöschung führt, wenn man es in einer echten Programmiersprache realisiert. D.h. man müsste entweder - vorher prüfen, ob die Eingabeparameter mit der Datenbreite verarbeitbar sind, oder - den Algorithmus irgendwie umschreiben, so dass das Problem entschärft wird, oder - einen alternativen Algorithmus erdenken. |
|||||||||
02.03.2023, 11:18 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Mein Fazit: Vorsicht bei der C-Portierung mit diesem Nuitka, wenn das zugrunde liegende Python-Programm auf einen größeren Integerbereich baut. Wenn man dennoch dann mit dem C/C++ dort arbeiten will (etwa aus Performance-Gründen), dann sollte man die int-Variablen, bei denen mehr Stellen benötigt werden, durch geeignete Datentypen austauschen. Ich habe da gute Erfahrungen mit der gmplib gemacht. |
|||||||||
02.03.2023, 12:04 | Finn_ | Auf diesen Beitrag antworten » | |||||||
Entfaltung der Rechnungen führt zu Da lässt sich zumindest kürzen. Zum Debuggen ließe sich die Entfernung von Überlaufprüfungen bei gcc und clang mit der Option -ftrapv verhindern. @HAL Das C-Programm ist natürlich handgeschrieben. Das von Nuitka erzeugte Programm rechnet dagegen mit PyObject, linkt also wohl die Laufzeit-Bibliothek von CPython samt Langzahlarithmetik hinzu. |
|||||||||
02.03.2023, 13:05 | GMath | Auf diesen Beitrag antworten » | |||||||
@HAL9000: Ich muss Dir widersprechen. Das Problem liegt m.E. NICHT bei der automatischen C-Portierung durch Nuitka. (Der Algorithmus kommt so harmlos daher, dass ein manuell geschriebenes Programm dafür nicht viel anders aussähe - jedenfalls wenn ich es schriebe). Nein, das Problem ist die "versteckte" numerische Instabilität bzw. Stellenauslöschung des Algorithmus selbst bei kleinen Eingabedaten. Das kann offenbar hinter jeder Ecke lauern. Wenn man das identifiziert hat, können - wenn man Glück hat - Umformungen helfen. Letztlich sollte man wohl eine (nicht-triviale) Analyse machen, welche Datenbreite für die vorgegebene Eingabe erforderlich ist und dann entsprechend anfordern. Das Gemeine eben: Ganz schön unerwartet. Jedenfalls wenn man kein Numerik-Profi ist, der das wohl auf den ersten Blick sieht. |
|||||||||
02.03.2023, 13:16 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Das mit dem Widersprechen gebe ich dir zurück: Bei Integerzahlen mit Integerarithmetik gibt es keine Stellenauslöschung, sondern nur Bereichsüberlauf. Der Original-Algorithmus von Finn_ hat nicht mit Floating-Point-Zahlen gearbeitet, sondern rein mit Integerzahlen. Und solange die (wie in Python) keine solchen Bereichsgrenzen kennen, ist auch alles in Ordnung: Weder Stellenauslöschung noch numerische Instabilitäten, weder versteckt noch offen. Das einzige, was diesen Algorithmus aus dem Tritt bringen könnte wären wohl Speicherplatzprobleme - was aber kaum anzunehmen ist, dass das mal passieren könnte. ![]() |
|||||||||
02.03.2023, 13:28 | GMath | Auf diesen Beitrag antworten » | |||||||
OK, "Stellenauslöschung" ist in diesem Fall nicht das Problem. Aber Bereichsüberlauf eben schon, denn in einem Produktivsystem würde kaum je Python verwendet. M.a.W. das Problem ist vorhanden und ziemlich gefährlich. |
|||||||||
02.03.2023, 13:29 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Das habe ich ja gesagt. Inwiefern du mir da "widersprichst", kann ich jetzt nicht nachvollziehen. ![]() Ich kenne dieses Nuitka nicht, ich hatte oben angenommen, dass dieses Programm die automatische Umwandlung von Python-Integern in C-int vorgenommen hatte (was Finn_ inzwischen korrigiert hatte). Und das, nur das habe ich als Problem benannt. |
|||||||||
02.03.2023, 13:33 | GMath | Auf diesen Beitrag antworten » | |||||||
Vermutlich missvestehen wir uns. Mir ist es wichtig, in diesem Thread hervorzuheben, dass, wenn man den Algorithmus tatsächlich implementiert (in einem System, dass keine dynamische Datenbreiten-Anpassung macht), man sich sehr vorsehen muss, weil schon bei kleinen Eingaben unerkannt Überläufe entstehen. |
|||||||||
03.03.2023, 09:30 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Ich weiß nicht, ob es ein Missverständnis ist, wenn jemand laut verkündet "Ich muss Dir widersprechen", und es dann am Ende gar nicht tut. Bei mir kommt sowas gar nicht gut an, aber das hast du wohl inzwischen gemerkt. |
|||||||||
03.03.2023, 10:04 | GMath | Auf diesen Beitrag antworten » | |||||||
Mir ist es wichtig, in diesem Thread hervorzuheben, dass, wenn man den Algorithmus tatsächlich implementiert (in einem System, das keine dynamische Datenbreiten-Anpassung macht), man sich sehr vorsehen muss, weil schon bei kleinen Eingaben unerkannt Überläufe entstehen. |
|||||||||
03.03.2023, 12:38 | Finn_ | Auf diesen Beitrag antworten » | |||||||
Überlaufprüfung beinhaltende Implementierung in Rust
|
|||||||||
03.03.2023, 12:55 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Was ist nur aus dem schönen übersichtlich klaren Python-Code geworden? Er ist zu einem Monster mutiert, wenn auch einem sicheren Monster. ![]() |
|||||||||
03.03.2023, 13:34 | GMath | Auf diesen Beitrag antworten » | |||||||
Soweit ich das sehe ist Python bei bestimmten Anwendungen unbedingt sinnvoll. Für - Demostration/ Edukation - Rapid Prototyping und für - Steuerung auf hohem Niveau (Scripting). Aber für eine Produktiv-Anwendung auf unterem Niveau ist es sicher nicht geeignet. ("Es tut mir leid Dave - das kann ich nicht tun.") Und mit anderen Programmiersprachen hat man dann eben einfach keine andere Wahl, als ein "Monster" zu programmieren; insbesondere wenn die Sache numerisch instabil ist. @Finn_ WOW! Herzlichen Dank. ![]() Ich hoffe, dass die realisierten Mechanismen für den einen oder anderen, der hier vorbeikommt, ein Hinweis/ Hilfe sein werden. (Ich selbst muss mir das jetzt mal in Ruhe anschauen) |
|||||||||
03.03.2023, 13:40 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Es sagt doch keiner, dass man C/C++ mit einem der Standard-Int-Datentypen nehmen MUSS. Ich hatte oben auf die gmplib verwiesen: Mit der kann man genauso arbeiten wie mit Python-Integer, in C++ durch Operatoren-Überladung sogar quasi in gewohnter Syntax - verwendet man Datentyp "mpq_class", sogar mit Brüchen beliebiger Genauigkeit. Man hat also durchaus eine Wahl - "alternativlos" war gestern. ![]() P.S.: Verständnis habe ich allenfalls für den Fall, dass du den Algorithmus auf einem kleinen Mikrocontroller implementieren musst, wo also eher in kByte statt MByte Ressourcen gerechnet wird. Dort könnte die gmplib in der Tat ein zu großer Brocken zum Dazulinken sein. ![]()
|
|||||||||
03.03.2023, 14:30 | GMath | Auf diesen Beitrag antworten » | |||||||
Sieht super aus, danke! Obwohl ich derjenige bin, der die Frage ursprünglich gestellt hat, traue ich mich nicht, ein Resumee zu ziehen. Nur soviel: Wenn jemand vor dem Problem steht: Eine "Restklassen-Zauberei" o.ä. zur direkten Bestimmung des Optimums scheint es nicht zu geben; man muss durchsuchen. Ein sehr guter (wenn nicht sogar optimaler) Ablauf ist die Traversierung des Stern-Brocot-Baums. Und das Wichtigste: Obwohl es so harmlos aussieht, ist der Algorithmus offenbar numerisch instabil, schon bei kleinen Eingaben! Wenn man das übersieht und "intuitiv" programmiert, wird man - i.d.R. ohne es zu bemerken - falsche Ergebnisse bekommen. Garantiert richtige Ergebnisse bekommt man nur, indem man dynamisch breite Datentypen verwendet Mit dem Preis von Laufzeit und Speicherbedarf. Muss man das begrenzen, so kann man bei vorgegebener Datenbreite eine Überlauferkennung verwenden mit dem Preis, dass die Lösung manchmal nicht gefunden wird, was aber immerhin auffällt. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |