Fliesskommazahl durch Bruch (Zähler/Nenner) annähern
FloatToFrac nähert eine beliebige, reelle Zahl durch einen Bruch an. Aus
0.333333333333 wird also
1/3 (d.h. Zähler=1, Nenner=3). Der Algorithmus arbeitet sehr schnell und findet den gekürzten Bruch in wenigen Iterationen.
Parameter
x: [in] Die reelle Zahl, die zerlegt werden soll.
Numerator: [out] Zähler des angenäherten Bruches. Positive oder negative, ganze Zahl.
Denominator: [out] Nenner des angenäherten Bruches. Positive, ganze Zahl.
Source
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:
| procedure FloatToFrac(const x: Extended; out Numerator, Denominator: Int64); const tol = 1e-12; var p, lastp, q, lastq, ptemp, qtemp, u, err, d: Extended; begin p := 1; q := 0; lastp := 0; lastq := 1; u := x;
repeat d := round(u); u := u - d;
ptemp := p*d+lastp; qtemp := q*d+lastq; lastp := p; lastq := q; p := ptemp; q := qtemp;
err := abs(p/q-x);
if (u=0) or (err<tol) or (x+err/4=x ) then break;
u := 1/u; until false;
if (p>high(Int64)) or (q>high(Int64)) or (p<low(Int64)) or (p<low(Int64)) then raise EIntOverflow.Create('FloatToFrac: Integer conversion overflow.');
if q < 0 then Numerator := -Trunc(p) else Numerator := Trunc(p); Denominator := abs(Trunc(q)); end; |
(*) Das letzte Abbruchkriterium sorgt dafür, dass die Rechnung abgebrochen wird, wenn der relative Fehler die Maschinengenauigkeit unterschreitet (d.h. es ist eine Notbremse, falls tol zu klein ist).
Anwendungsbeispiel
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7:
| procedure TForm1.ButtonClick(Sender: TObject); var Zaehler, Nenner: Int64; begin FloatToFrac(0.33333333333333, Zaehler, Nenner); ShowMessage(Format('%d/%d',[Zaehler, Nenner])); end; |
Mathematischer Hintergrund
Die eingegebene Zahl x wird folgendermassen entwickelt:
1
x = d1 + ------------------
1
d2 + -----------
1
d3 + ----
d4
etc.
Um eine solche Entwicklung zu kriegen, wird immer ein ganzzahliger Teil des Wertes abgezogen (das sind die d-Werte) und danach der Bruch gekehrt (1/x). Danach wird wieder ein ganzzahliger Teil abgezogen, usw.. Das ganze geschieht so oft, bis die Reihe konvergiert. Es gibt Beweise, die belegen, dass die Sache für Zahlen in Q konvergiert. Das Abbruchkriterium (siehe break-Statement) verhindert, dass die "Ungenauigkeit" der Float-Darstellung das korrekte Resultat versaut.
Näheres zu Kettenbrüchen:
en.wikipedia.org/wiki/Continued_fraction (Wikipedia)
Moderiert von jasocul: Beitrag geprüft am 05.04.2006
[meta]Bruch Zerlegung Zähler Nenner[/meta]