Autor Beitrag
delfiphan
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: Sa 03.09.05 00:32 
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
ausblenden volle Höhe Delphi-Quelltext
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// Fehlertoleranz
var
  p, lastp, q, lastq, ptemp, qtemp, u, err, d: Extended;
begin
  // Initialisierung
  p := 1;
  q := 0;
  lastp := 0;
  lastq := 1;
  u := x;

  repeat
    // Einen ganzzahligen Anteil abspalten
    d := round(u);
    u := u - d;

    // Update von p und q: Kettenbruch (siehe unten) nachführen. Es gilt: p/q ~= x
    ptemp := p*d+lastp;
    qtemp := q*d+lastq;
    lastp := p;
    lastq := q;
    p := ptemp;
    q := qtemp;

    // Approximationsfehler
    err := abs(p/q-x);

    // Abbruchkriterien
    if (u=0or (err<tol) or (x+err/4=x {sic!}then  // (*)
     break;

    // Bruch umkehren
    u := 1/u;
  until false;

  // Vor Integerkonversion auf Bereich überprüfen
  if (p>high(Int64)) or (q>high(Int64)) or
     (p<low(Int64)) or (p<low(Int64)) then
    raise EIntOverflow.Create('FloatToFrac: Integer conversion overflow.');

  // Vorzeichen von Nenner zum Zähler
  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
ausblenden 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])); // Ausgabe 1/3
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 user profile iconjasocul: Beitrag geprüft am 05.04.2006
[meta]Bruch Zerlegung Zähler Nenner[/meta]


Zuletzt bearbeitet von delfiphan am Mo 19.09.05 10:57, insgesamt 3-mal bearbeitet