Gesucht: Nächste rationale Zahl mit Nebenbedingung

Neue Frage »

GMath Auf diesen Beitrag antworten »
Gesucht: Nächste rationale Zahl mit Nebenbedingung
Hallo!

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).
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 . Augenzwinkern
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.
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. traurig
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 Augenzwinkern

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

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?
 
 
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.
Finn_ Auf diesen Beitrag antworten »

Binäre Suche im Stern-Brocot-Baum

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
def mediant(x, y):
    return (x[0] + y[0], x[1] + y[1])

def lt(x, y):
    return x[0]*y[1] < y[0]*x[1]

def dist(x, y):
    return (abs(x[0]*y[1] - y[0]*x[1]), x[1]*y[1])

def bisection(x, a, b):
    best = b
    while True:
        m = mediant(a, b)
        if lt(dist(m, x), dist(best, x)):
            best = m
            yield m
        if m == x: break
        if lt(m, x):
            a = m
        else:
            b = m

def approx(r, s):
    for (p, q) in bisection((r, s), (0, 1), (1, 0)):
        print("{}/{}".format(p, q))

approx(1000, 799)
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?
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).

Zitat:
Original von GMath
und findet dadurch i.allg. nicht das Optimum in
einem einschränkenden Rechteck?

So wie ich das verstehe, findet das Pythonscript ALLE Näherungsbrüche in genau dem von dir beschriebenem Sinne. Probier es aus!
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?
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.
GMath Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
...
P.S.: Langsam mutiert das zur Programmieraufgabe.


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

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!
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von GMath
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

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. Augenzwinkern
Finn_ Auf diesen Beitrag antworten »

Portierung auf C89

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
#include <stdlib.h>
#include <stdio.h>

typedef enum {false, true} bool;

typedef struct Fraction {
        int n; /* numerator */
        int d; /* denominator */
} Fraction;

Fraction fraction(int n, int d) {
        Fraction value;
        value.n = n;
        value.d = d;
        return value;
}

Fraction mediant(Fraction x, Fraction y) {
        return fraction(x.n + y.n, x.d + y.d);
}

bool lt(Fraction x, Fraction y) {
        return x.n*y.d < y.n*x.d;
}

Fraction dist(Fraction x, Fraction y) {
        return fraction(abs(x.n*y.d - y.n*x.d), x.d*y.d);
}

void bisection(Fraction x, Fraction a, Fraction b,
        void (*callback)(Fraction)
) {
        Fraction best = fraction(1, 0);
        while (1) {
                Fraction m = mediant(a, b);
                if (lt(dist(m, x), dist(best, x))) {
                        best = m;
                        callback(m);
                }
                if (m.n == x.n && m.d == x.d) break;
                if (lt(m, x)) a = m; else b = m;
        }
}

void print_fraction(Fraction m) {
        printf("%i/%i\n", m.n, m.d);
}

void approx(int r, int s) {
        Fraction a = fraction(0, 1);
        Fraction b = fraction(1, 0);
        bisection(fraction(r, s), a, b, print_fraction);
}

int main() {
        approx(1000, 799);
        return 0;
}
GMath Auf diesen Beitrag antworten »

Nuitka?

==> "Der Wodka ist gut, aber das Steak ist lausig"
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.
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).
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).
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von GMath
Ab 1e4/(1e4-1) mit 32 bit signed ist schon Schluss.

Versteh ich nicht - womit ist ab 10000/9999 "Schluss" im Zusammenhang mit 32Bit-Integerzahlen? Erstaunt1
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.
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

code:
1:
        if lt(dist(m, x), dist(best, x)):
macht den Überlauf-Ärger.
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.
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.
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.
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.
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. Augenzwinkern
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.
HAL 9000 Auf diesen Beitrag antworten »

Das habe ich ja gesagt. Inwiefern du mir da "widersprichst", kann ich jetzt nicht nachvollziehen. unglücklich

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.
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.
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.
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.
Finn_ Auf diesen Beitrag antworten »

Überlaufprüfung beinhaltende Implementierung in Rust

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
// Typalias, damit man kurzerhand von i32
// auf i64 oder i128 wechseln kann.
#[allow(non_camel_case_types)]
type int = i32;

// Ganzzahlen mit Überlaufprüfung.
// Es kodiert Int(None) den Wert bei Überlauf.
#[derive(Clone, Copy)]
struct Int(Option<int>);

// Formatierte Ausgabe
impl std::fmt::Display for Int {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self.0 {
            Some(value) => write!(f, "{}", value),
            None => write!(f, "undefinierter Wert")
        }
    }
}

// Operatorüberladung
impl std::ops::Add for Int {
    type Output = Int;
    fn add(self, y: Int) -> Int {
        Int(self.0.and_then(|x| y.0.and_then(|y| x.checked_add(y))))
    }
}

impl std::ops::Sub for Int {
    type Output = Int;
    fn sub(self, y: Int) -> Int {
        Int(self.0.and_then(|x| y.0.and_then(|y| x.checked_sub(y))))
    }
}

impl std::ops::Mul for Int {
    type Output = Int;
    fn mul(self, y: Int) -> Int {
        Int(self.0.and_then(|x| y.0.and_then(|y| x.checked_mul(y))))
    }
}

fn abs(x: Int) -> Int {
    Int(x.0.map(int::abs))
}

// Der Rest verläuft wie gehabt. Die Fragezeichen sind Wächter,
// die Überlauf ähnlich wie bei Ausnahmen an die aufrufende
// Funktion weiterreichen.

#[derive(Clone)]
struct Fraction {
    n: Int, /* numerator */
    d: Int  /* denominator */
}

fn fraction(n: int, d: int) -> Fraction {
    Fraction {n: Int(Some(n)), d: Int(Some(d))}
}

fn mediant(x: &Fraction, y: &Fraction) -> Fraction {
    Fraction {n: x.n + y.n, d: x.d + y.d}
}

fn lt(x: &Fraction, y: &Fraction) -> Option<bool> {
    Some((x.n*y.d).0? < (y.n*x.d).0?)
}

fn dist(x: &Fraction, y: &Fraction) -> Fraction {
    Fraction {n: abs(x.n*y.d - y.n*x.d), d: x.d*y.d}
}

fn bisection(x: Fraction, mut a: Fraction, mut b: Fraction,
    callback: &mut dyn FnMut(&Fraction)
) -> Option<()>
{
    let mut best = fraction(1, 0);
    loop {
        let m = mediant(&a, &b);
        if lt(&dist(&m, &x), &dist(&best, &x))? {
            best = m.clone();
            callback(&m);
        }
        if m.n.0? == x.n.0? && m.d.0? == x.d.0? {return Some(());}
        if lt(&m, &x)? {a = m;} else {b = m;}
    }
}

fn approx(r: int, s: int) {
    let a = fraction(0, 1);
    let b = fraction(1, 0);
    let result = bisection(fraction(r, s), a, b, &mut |m| {
        println!("{}/{}", m.n, m.d)
    });
    if result.is_none() {
        println!("Überlauf. Programm abgebrochen.");
    }
}

fn main() {
    approx(1000, 799);
}
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. Big Laugh
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. smile
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)
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von GMath
Und mit anderen Programmiersprachen hat man dann
eben einfach keine andere Wahl, als ein "Monster"
zu programmieren; insbesondere wenn die Sache
numerisch instabil ist.

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

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

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
#include <iostream>
#include <gmpxx.h>

mpq_class mediant(mpq_class x, mpq_class y)
{
    return mpq_class(x.get_num() + y.get_num(), x.get_den() + y.get_den());
}

void approx(mpq_class x)
{
    mpq_class a(0, 1);
    mpq_class b(1, 0);
    mpq_class best = a;
    while (true)
    {
        mpq_class m = mediant(a, b);
        if (abs(m - x) < abs(best - x))
        {
            best = m;
            std::cout << m << std::endl;
        }
        if (m == x)
        {
            break;
        }
        if (m < x)
        {
            a = m;
        }
        else
        {
            b = m;
        }
    }
}

int main (int argn, char *argc[])
{
    approx(mpq_class("1000/799"));
    return 0;
}
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.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »