Ich habe eine Gleitkommazahl und möchte daraus einen Bruch erstellen. Da es durchaus vorkommen kann, dass des keinen exakten Bruch gibt, möchte ich den bestmöglichen Bruch verwenden. Wie kann man diesen ermitteln, ohne alle möglichen Kombinationen durchspielen zu müssen ? Konkret geht es um eine PLL. Ich gebe die gewünschte Ausgangsfrequenz vor, und der uC (ein kleiner AVR) soll daraus die Werte für den PLL bestimmen: f=(2 x 14.31818MHz x P/Q)/D
Am einfachsten geht es binaer - genau so, wie es selbst im Rechner umgerechnet wird, also 0.5 ist 1/2, 0.25 - 1/4, 0.125 - 1/8 und so weiter. Wenn man so macht, dann kriegt man aus 0.7 0.1011.... Es ist doch klar, das es ein Bruch sein sollte (1/2 + 1/8 + 1/16 z.B. = 11/16). Ich glaube, dass man den Algorithmus aus dem GCC nehmen koennte.
Genauso geht es auch mit Dezimalzahlen ab,xyz = a*10 + b*1 + x*1/10 + y*1/100 + z*1/1000
Sind das getrennt einstellbare Referenz - und Oszillatorteiler? Dann gibt es vermutlich eine sehr große Zahl von möglichen Quotienten, die der gewünschten Frequenz nahekommen - ich fürchte, dafür gibt es keine geschlossene Lösung. ich hatte auch schon mal das Problem, eine Siemens-PLL auf möglich kleine Schrittweite bei gegebenem Referenzquarz einzustellen, und habe am Schluß eine Tabelle in ein Eprom geschrieben, anders ging es nicht. ein ähnliches Problem - eine Tabelle aller mit den Widerständen der E24 oder E96-Reihe möglichen Quotienten aufsteigend sortiert - ist auch nur mit Berechnen und anschließendem Sortieren möglich
Hm... also bei Float ist es schwer, aber wenn du dich auf eine Fixkommastelle einigen kannst ginge es so: 12.09875 = 1209875/100000 Das kanst du dan noch versuchen gegen zu kürzen in diesem Falle z.B. mit 5 wenn du das mit den ersten 10 Zahlen versuchst solltest du schon auf einen einigermassen guten Bruch kommen (0.24 ist z.b. 24/100 ist durch 2 kürzbar: 12/50 ist durch 2 kürzbar = 6/25 ist nicht kürzbar durch 2, 3, 4, 5 ... also zu ende gekürzt) Ist natürlich etwas aufwand in enr Schleife aber sollte schafbar sein.
@Läubi, netter Einfall! Ich denke das kann noch vereinfacht werden. Da Du immer Zehnerpotenzen nimmst, kann das kürzen noch wie folgt gemacht werden: 10=2*5 100=10^2=(2*5)^2 usw. d.h. Du brauchst nur durch zwei und fünf dividieren. Voila. Allerdings hat die Sache einen Haken: sowas wie bsp. 22/7 für PI wird dabei nicht rauskommen, da die "probierten" Teiler vielfache von 2 und/oder fünf sind. Gruß Mario
> Ich habe eine Gleitkommazahl und möchte daraus einen Bruch > erstellen. Da es durchaus vorkommen kann, dass des keinen > exakten Bruch gibt, In Mathe wohl nicht aufgepasst? Wie ist denn eine Rationale Zahl definiert? Doch nicht etwa als Bruch aus einer ganzen Zahl und einer natürlichen Zahl?!?! Naja, und den Bruch hast Du in Deiner Gleitkommadarstellung ja schon, nämlich die Mantisse. Was genau ist eigentlich Dein Problem? Was willst Du überhaupt berechnen?
> sowas wie bsp. 22/7 für PI wird dabei nicht rauskommen
Das kommt garantiert nicht raus...
Denn PI ist eine irrationale Zahl, und keine rationale Zahl...
Hm... ja ich denke das läßt sich noch optimieren, aber das sit u.A. ne gute möglichkeit im Kopf Brüche auszurechnen, aber es gibt bestimmt auch nen Anderen/Einfachen Algorithmus, weil jeder Billig Taschenrechner kann ja heutzutage sowas relativ gut. Also erzähl doch mal was genau du vor hast, eventuell läßt sich das ganze sogar einfacher mit einer Tabelle lösen?
Hier mal ein konkretes Beispiel: P/Q=2,7587 Mach ich es mal nach dem Läubi Verfahren: 2,7587=27587/10000 Das ganze kann man durch 5 teilen: P/Q=5157/2000 weiter geht nichts. Da P und Q aber 7bit Zahlen sind geht es so nicht. Wenn ich das nach dem Binärverfahren mache, dann bekomme ich doch nur 1,2,4,8,16,32,64 für den Nenner, oder ? In diesem Beispiel wären das 2+1/2+1/4+1/128+1/2048 Addiere ich das auf, komme ich auf 11/4=2,75. Das ist ziemlich weit vom gewünschten Wert weg... Auf eine Tabelle möchte ich verzichten, da ich am Ende eine beliebige Frequenz eingebe, und der PLL diese so genau wie möglich erzeugen soll. Wenn ich das nach dem Try&Error Prinzip mache, also mit Q=1 und P=1 anfange und alles solange erhöhe bis ich bei 127 und 127 angekommen bin, und mir die Kombination mit dem kleinsten Fehler merke brauche ich 16384 möglichkeiten. Wenn ich von ms für eine float Berechnung ausgehe, dann dauert es über 10s und das ist eindeutig zu lange. Macht mal Vorschläge, mal schauen wer am nähesten an die 2,7587 ran kommt...
mit 7 bit wirst du da fürchte ich dann nicht weit kommen, und 2,75 ist
dch shcon recht nah an 2,7587 wie genau muß den das ganze sein?
Ich meine du kanst ja sogar die Tests einschränken, wenn du es
interativ verwendest, weil z.b. wenn die Zahl > 1 ist mußt du ja Zahlen
die sowieso Zahlen ergeben die immer kleiner 1 sind (also z.b. 1 / 7 ist
immer < 1 muß also garnicht ausprobiert werden).
for (i=1;i<127;i++) {
for (j=1;j<127;j++) {
if (i>j) teste
}
}
Oder du benuzt die Binärmethode und gehst von dort aus:
Wenn der Fehler kleiner geht -> Mache weiter, wenn der fehler größer
wird -> abbrechen
Hallo Benedikt, nimm P/Q=80/29, stimmt glaub ich ganz gut (2,7586206896551726) :). Ich hab das noch im Hinterkopf gehabt, das es sowas gibt: Lösung Kettenbrüche. Da kannst Du das online machen. http://www.arndt-bruenner.de/mathe/scripts/bruchrechnung1.htm#kettenbruch unter: Approximation von Dezimalbrüchen durch echte Brüche Den Algorithmus kannst Du Dir direkt aus dem java-skript holen. Die Erklärung gibts hier: http://de.wikipedia.org/wiki/Kettenbruch @Unbekannter: ... der Du ja am besten von allen in Mathe aufgepasst hast, kannst nachlesen was bei irrationalen Zahlen passiert. Zumindest hast Du Dich als nicht Bastler geoutet, sonst wüsstest Du von dem Problem bescheid ... Gruß Mario
Die Lösung 80/29 für 2,7587 stimmt. Die Kettenbruckmethode sieht gut ist, allerdins scheint das ganze relativ aufwendig zu sein, wenn ich mir so den Java Code anschaue. Ob dafür 2kByte Flash reichen ?
Abwechselnd Zähler und Nenner erhöhen und vergleichen, ob zu groß oder zu klein ( Wägemethode ähnlich der AD-Wandlung mit sukzessiver Approximation). Die Werte müßten dann um den Sollwert herum pendeln, und den nächstgelegenen kann man am Schluß nehmen. Bei 2*7Bit ist das noch nin endlicher Ziet machbar. Ich wollte mal die Trägerfrequenz eines UHF-Fernsehsenders in eine Normalfrequenz herunterteilen, mit einem n/m-Impulsverschluckzähler. Diese Frequenzen haben ziemlich krumme Werte, mit der Farbträgerfrequenz 4,433MHz irgendwie verknüpft um die Störungen zu minimieren, daher war das eine ziemliche Rechnerei, aber nach der genannten Methode habe ich Brüche gefunden, die auf 10 Stellen genau stimmten.
@Benedikt,
Also sooo kompliziert ist das nun auch nicht ....
In Matlab sieht das qanze so aus:
k=[];
number = 2.7587;
r = 10000;
q = number * r;
% Erstelle den Kettenbruch
for i=1:5
k(i) = floor(q/r);
h = r;
r = mod(q, r);
q = h;
end
% Errechne aus dem Kettenbruch p und q.
p=k(5);
q=1;
for i=4:-1:1
h=p;
p=k(i)*p+q;
q=h;
end
Danach ist p=80 und q=29.
Wenn Du's aber umständlich machst, wirst Du 2k sicher voll kriegen -
kein Zweifel :).
Gruß
Mario
Sollwert = 2,7587 Anfangswert 2/1 =2 zu klein, also Zähler erhöhen 3/1 =3 zu groß, also Nenner vergrößern 3/2 =1,5 zu klein, Zähler erhöhen 4/2 =2 immer noch zu klein 5/2 =2,5 immer noch zu klein 6/2 =3 zu groß 6/3 =2 zu klein und so weiter, das sollte ja zum Ziel führen
Ergänzung zu meinem obrigen Beitrag: Kann natürlich alles in integer-Arithmetik gemacht werden, und mit ein bisschen überlegen auch noch viel effizienter gestaltet (Hifsvariable h kann wahrs. eleminiert werden). Das denke ich ist auch der Hauptvorteil gegenüber Christoph's Ansatz - der aber sonst auch sehr nett ist.
Auch wenn der Thread schon steinalt ist, ich aber vor dem gleichen Problem stehe/stand und möglicherweise es noch weitere suchenden interessiert. Ich habe eine Lösung bei der nur eine Variable druchprobiert werden muss:
1 | private void convertAndStore(double value) { |
2 | //calculate best fitting a/b value
|
3 | double error = Double.MAX_VALUE; |
4 | int besta = 1, bestb = 1; |
5 | int b = 1; |
6 | while ((error > 0) && (b < 65555)) { |
7 | int a = (int)(value*((double)b)); //+0.5 for rounding? |
8 | double nerror = Math.abs(((double)a)/((double)b) -value); |
9 | if (a > 65555) //all following numbers will be even greater |
10 | break; |
11 | if ((nerror < error)){ |
12 | error = nerror; |
13 | besta = a; |
14 | bestb = b; |
15 | }
|
16 | b++; |
17 | }
|
18 | //now store besta and bestb
|
19 | }
|
konkret darf eben a und b nur im Bereich einer unsigned 16 Bit Variable liegen und ich war auf der Suche nach einer besseren Methode. Hätte ich die Begrenzung nicht, würde ich bei dem Nenner "das Komma streichen" und dann als Zähler 10^(Zahl der Nachkommastellen) setzen. Dann von Nenner und Zähler den ggt bestimmen und entsprechend teilen.
Weils mich selber interessiert hat, habe ich das Verfahren von Christoph mal als Exceltabelle "nachprogrammiert" angefangen wird mit 1/1 und anschließend wird Zähler bzw Nenner erhöht. Einfach in die Exceltabelle oben links den gewünschten Wert eingeben. Die Treffer werden dann markiert und ich komm auf die gleiche Werte wie hier im Thrad geposted wurden. (z.B. 22/7 für PI) Gruß Roland
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.