Matroids Matheplanet Forum Index
Moderiert von Bilbo matph
Matroids Matheplanet Forum Index » Informatik » bester Bruch zu einem float
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich bester Bruch zu einem float
SebOeh
Junior Letzter Besuch: im letzten Monat
Dabei seit: 22.03.2019
Mitteilungen: 8
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-04-14


Hallo,

um meine sehr eingemottete Java-Kenntnisse aufzufrischen, schreibe ich gerade ein Programm, das mit Brüchen rechnen soll. Zähler und Nenner sind dabei vom Typ int, es muss aber intern für Summen mit long und sogar mit BigInteger für Multiplikationen oder Operationen arbeiten.
Nun habe ich das Problem, wie verwandle ich eine beliebige float-Zahl in einen Bruch, der mit einer gewissen Fehlertoleranz den besten Bruch darstellt.
Also stellen wir uns vereinfacht das so vor:
Für Zähler und Nenner sind natürliche Zahlen bis 100 erlaubt
ich habe die Zahl 0,72857 und möchte den besten Bruch dafür finden.

Den besten Zähler für einen bestimmten Nenner ist easy. Den besten Bruch zu finden ist aber extrem schwierig, da die Folge nicht stetig konvergiert. Ich muss also alle Nenner durchsuchen. Wenn Nenner irgend ein int sein darf, dauert jede Umwandlung viel zu lange für einen akzeptablen Konstruktor.

Beispiel: float= 0,72857 (in etwa 51/70). Gerundet auf 5 Kommastellen:

Bruch = 1 / 1       Differenz= 0,27143
Bruch = 1 / 2       Differenz= 0,22857
Bruch = 2 / 3       Differenz= 0,0619
Bruch = 3 / 4       Differenz= 0,02143
Bruch = 4 / 5       Differenz= 0,07143
Bruch = 4 / 6       Differenz= 0,0619
Bruch = 5 / 7       Differenz= 0,01428
Bruch = 6 / 8       Differenz= 0,02143
Bruch = 7 / 9       Differenz= 0,04921
Bruch = 7 / 10      Differenz= 0,02857
Bruch = 8 / 11      Differenz= 0,0013
...
Bruch = 48 / 66     Differenz= 0,0013
Bruch = 49 / 67     Differenz= 0,00277
Bruch = 50 / 68     Differenz= 0,00672
Bruch = 50 / 69     Differenz= 0,00393
Bruch = 51 / 70     Differenz= 0
Bruch = 52 / 71     Differenz= 0,00382
Bruch = 52 / 72     Differenz= 0,00635
Bruch = 53 / 73     Differenz= 0,00254


Man sieht dass die Differenz zu höheren Nenner nicht stetig weniger wird, sondern nur "zappelt".

Gibt es da irgendein Algorithmus dafür?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Fabi
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.03.2002
Mitteilungen: 4574
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-04-14


Hallo Seb,

Es gibt einen relativ einfach zu implementierenden (aber nicht unbedingt leicht einzusehenden) Algorithmus; siehe zum Beispiel math.stackexchange.com/questions/2555205/best-rational-approximation-with-numerator-denominator-less-than-255

Stichwörter sind Stern-Brocot-Tree und Farey sequences.

vG,
Fabi




-----------------
"There would be the mathematical equivalent of worldwide rioting." (P.C.)

Willst du Hamburg oben sehen, musst du die Tabelle drehen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1379
Wohnort: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2021-04-14


2021-04-14 12:38 - SebOeh im Themenstart schreibt:
Gibt es da irgendein Algorithmus dafür?

Hi SebOeh,

Ja, du kannst eine Kettenbruchentwicklung durchführen. Bricht man diese nach einer beliebigen Iteration ab, bekommt man eine sehr gute Näherung für die reelle Zahl. Diese hat sogar die Eigenschaft, dass es keine bessere Näherung mit kleinerem Nenner gibt.

Siehe z.B. folgenden Kalkulator.

Kay

[Die Antwort wurde vor Beitrag No.1 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2928
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2021-04-14


Die Kettenbruchentwicklung liefert leider nicht zwangsläufig den besten Bruch bei gegebener Nennerobergrenze.

Daher wäre wohl der genannte Stern-Brocot-Algorithmus die einfachste Lösung.




-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6993
Wohnort: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2021-04-14


2021-04-14 13:35 - DerEinfaeltige in Beitrag No. 3 schreibt:
Die Kettenbruchentwicklung liefert leider nicht zwangsläufig den besten Bruch bei gegebener Nennerobergrenze.

@DerEinfaeltige: Danke für den Hinweis! 👍 Bis eben dachte ich noch, dass das so wäre. Aber da habe ich den mir bekannten Satz falsch interpretiert.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
SebOeh hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]