Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Wie löst man a ≈ x/y ohne rohe Gewalt?

Wie löst man a ≈ x/y ohne rohe Gewalt?

Universität / Fachhochschule

Tags: mehrere Unbekannte

einfallslos2 aktiv_icon

08:41 Uhr, 30.03.2024

Ich würde gerne die folgende Formel lösen:
a ≈

\frac{x}{y}

Das folgende is bekannt:

a = \frac{a 1}{a 2}

a 1, a 2, x

und

y

sind Ganzzahlen.

a, a 1

und

a 2

haben jeweils einen bekannten Wert.

x

und

y

haben unbekannte Werte.

Der Unterschied zwischen a und

\frac{x}{y}

soll gering sein.

x

und

y

müssen beide jeweils einen Wert zwischen 1 und

16.777.215

haben.

a 1

und

a 2

können beide größer als

16.777.215

sein.

Die einzige Möglichkeit, welche ich kenne, besteht darin, alle Möglichkeiten durchzuprobieren und nach jedem Probieren einen Vergleich durchführen, ob ich bereits bessere Werte für

x

und

y

gefunden habe.

Kennt jemand eine bessere Lösung?

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

calc007

09:19 Uhr, 30.03.2024

Hallo
Für

a_{i} \leq 16777215

ist das Problem ja trivial. Das wirst du nicht meinen.

Eine spontane Algorithmus-Einschränkung / Verkürzung, die du vielleicht schon bedacht aber noch nicht benannt hast, ist ja bestimmt, eine Fallunterscheidung zu tätigen:

a)

Für den Fall

a_{1} > a_{2}

betrachtest du natürlich nur die Zahlen

y,

die innerhalb von

\frac{a_{2}}{a_{1}} \cdot 16777215

liegen.

b)

Für den Fall

a_{1} < a_{2}

betrachtest du natürlich nur die Zahlen

x,

die innerhalb von

\frac{a_{1}}{a_{2}} \cdot 16777215

liegen.

Aber zugegeben, das ist noch kein großer Fortschritt und immer noch eine elende Sucherei...

PS:
Und ebenso naheliegend:
Algorithmus abbrechen, wenn du eine echte Ganzzahl-Division gefunden hast.

einfallslos2 aktiv_icon

10:07 Uhr, 30.03.2024

Ja genau, es geht um den Fall, dass

a 1

oder

a 2 > 16.777.215

ist.

Achso, ja, danke für den Hinweis, das steht nicht in der Frage:

a 1

ist bei mir immer

\leq a 2

deshalb ist automatisch

x

immer

\leq y

.

Jemand von Intel hat das Problem so gelöst:

x = a 1

y = a 2

while(y

> 16.777.215) {

x \Rightarrow > 1

y \Rightarrow > 1

}

Für die Nicht-Programmierer:

x \Rightarrow > 1

bedeutet, dass

x

durch 2 geteilt wird.

Also quasie wie beim Kürzen. Aber ich glaube dadurch erreicht man nur ein suboptimales Ergebnis, weil die Nachkommastellen bei Ganzzahlen bei jedem Teilen verloren gehen. Außerdem lässt die Schleife noch Potential offen, den Ablauf zu beschleunigen.

einfallslos2 aktiv_icon

10:24 Uhr, 30.03.2024

Achso, jetzt habe ich es kapiert. Oh man, ich bin so dumm.

Ich benutze einfach

16.777.215

für

y

und berechne dann

x

. Das ist vielleicht nicht die bestmögliche Kombination von

x

und

y

aber eine relativ schnelle Lösung.

calc007

12:19 Uhr, 30.03.2024

Ich kenne den Syntax nicht, aber wenn "x

\to > 1

tatsächlich praktisch eine Division durch 2 bedeuten sollte, dann bedeutet das doch, dass praktisch nur

24

Möglichkeiten der

2^{24}

potenziellen Kandidaten durchprobiert werden.
Das ist natürlich schnell, aber noch weit, weit entfernt von
"...alle Möglichkeiten durchzuprobieren und nach jedem Probieren einen Vergleich durchführen",
um das echte Optimum zu erforschen.

KartoffelKäfer aktiv_icon

17:32 Uhr, 30.03.2024

y := 16777215,

x := C i n t (\frac{a_{1}}{a_{2}} \cdot y)

C i n t

ist ein Basic-Befehl für kaufmännisch runden.

Der Fehlerbetrag ist dann kleinergleich

| \frac{a_{1}}{a_{2}} - \frac{\frac{a_{1}}{a_{2}} \cdot y \pm \frac{1}{2}}{y} | = \frac{1}{2 \cdot y} = \frac{1}{2 \cdot 16777215}

HJKweseleit aktiv_icon

22:23 Uhr, 30.03.2024

Stichwort: Kettenbruchentwicklung mit Abbruch.

einfallslos2 aktiv_icon

23:22 Uhr, 30.03.2024

@calc007: Ja, das ist richtig. Aber ich dachte ich veröffentliche die suboptimale Lösung als Denkanstoß trotzdem. Die Endlösung ist übrigens aus einer Kombination von Ihrem Denkanstoß (dass lediglich jener Fall gelöst werden muss, in welchem

a 2 > 16.777.215

ist) und Intels Lösung entstanden.

KartoffelKäfer hat dann noch zur Vervollständigung den maximalen Fehler berechnet. Schritt für Schritt sind wir so zum Ziel gekommen.

Das "x

= > >

1" bedeutet übrigens: Um 1 Binärstelle nach rechts schieben und entspricht deshalb einer Division durch 2. Für das Ausführen von einem Schiebebefehl ist 1 Maschinenzyklus notwendig. Für die Ausführung von einem Divisionsbefehl sind etwa

40

Maschinenzyklen notwendig.

HAL9000

07:36 Uhr, 31.03.2024

Stichwort: Stern-Brocot

Damit kann man mit geringem Rechenaufwand bei vorgegebener oberer Schranke für den Nenner

y

den optimalen Näherungsbruch

\frac{x}{y}

für

a

bestimmen. Hier ist sogar ein Python-Skript dafür zu finden:

www.matheboard.de/thread.php?postid=2224264#post2224264

Wennn du beispielsweise im verlinkten Skript approx(728194023, 1973482019) aufrufst, dann werden alle besten rationalen Näherungsbrüche von

\frac{728 194 023}{1 973 482 019}

ausgegeben, das sind

1/2
1/3
2/5
3/8
4/11
7/19
24/65
31/84
38/103
69/187
238/645
307/832
376/1019
1059/2870
1435/3889
3246/8797
4681/12686
10797/29261
15478/41947
51115/138527
66593/180474
82071/222421
97549/264368
405674/1099419
503223/1363787
600772/1628155
698321/1892523
5684117/15404552
6382438/17297075
7080759/19189598
7779080/21082121
8477401/22974644
9175722/24867167
9874043/26759690
10572364/28652213
31018771/84064116
41591135/112716329
218528039/592233858
260119174/704950187
301710309/817666516
343301444/930382845
384892579/1043099174
728194023/1973482019

Dein Ansinnen ist, dass Zähler wie Nenner

< 2^{24}

sind, damit wäre der beste Näherungsbruch unter diesen Rahmenbedingungen dann

\frac{5 684 117}{15 404 552}

, der absolute Approximationsfehler ist dabei

∣ \frac{5 684 117}{15 404 552} - \frac{728 194 023}{1 973 482 019} ∣ = \frac{473}{15 404 552 \cdot 1 973 482 019} < 1.56 \cdot 1 0^{- 14}

.

Man kann natürlich das Skript leicht so umgestalten, dass nur genau dieser letzte passende Näherungsbruch ausgegeben wird und dann abgebrochen wird.

@HJKweseleit

Die Kettenbruch-Näherungswerte tauchen sämtlich in dieser Liste auch mit auf, aber i.a. nicht nur diese, sondern auch noch welche "dazwischen". Der im obigen Beispiel gefundene Bruch ist ein solcher "dazwischen", d.h. die letzte Kettenbruchapproximation

\frac{698 321}{1 892 523}

mit Nenner

< 2^{24}

ist dann doch geringfügig schlechter hinsichtlich der absoluten Genauigkeit der Approximation.

1584118

1584095

	Status: nicht eingeloggt	Noch nicht registriert?