Algorithmus für die Suche nach dem Verhältnis von zwei floating-point-zahlen?
Brauche ich, um das Verhältnis von einer Gleitkommazahl in eine andere, und das Verhältnis benötigt werden zwei Ganzzahlen. Zum Beispiel:
- Eingang:
1.5, 3.25
- Ausgabe:
"6:13"
Kennt jemand eine? Die Suche im internet, fand ich keinen solchen Algorithmus noch ein Algorithmus für das kleinste gemeinsame Vielfache oder Nenner von zwei floating-point-zahlen (nur ganze zahlen).
Java-Implementierung:
Dies ist die endgültige Implementierung, die werde ich verwenden:
public class RatioTest
{
public static String getRatio(double d1, double d2)//1.5, 3.25
{
while(Math.max(d1,d2) < Long.MAX_VALUE && d1 != (long)d1 && d2 != (long)d2)
{
d1 *= 10;//15 -> 150
d2 *= 10;//32.5 -> 325
}
//d1 == 150.0
//d2 == 325.0
try
{
double gcd = getGCD(d1,d2);//gcd == 25
return ((long)(d1 / gcd)) + ":" + ((long)(d2 / gcd));//"6:13"
}
catch (StackOverflowError er)//in case getGDC (a recursively looping method) repeats too many times
{
throw new ArithmeticException("Irrational ratio: " + d1 + " to " + d2);
}
}
public static double getGCD(double i1, double i2)//(150,325) -> (150,175) -> (150,25) -> (125,25) -> (100,25) -> (75,25) -> (50,25) -> (25,25)
{
if (i1 == i2)
return i1;//25
if (i1 > i2)
return getGCD(i1 - i2, i2);//(125,25) -> (100,25) -> (75,25) -> (50,25) -> (25,25)
return getGCD(i1, i2 - i1);//(150,175) -> (150,25)
}
}
->
gibt an die nächste Stufe in der Schleife oder den Aufruf der Methode
Mystische Umsetzung als Java:
Obwohl ich nicht mit dazu, es mehr als verdient anerkannt zu werden, so übersetzte ich es auf Java, also ich könnte es verstehen:
import java.util.Stack;
public class RatioTest
{
class Fraction{
long num;
long den;
double val;
};
Fraction build_fraction(Stack<long> cf){
long term = cf.size();
long num = cf[term - 1];
long den = 1;
while (term-- > 0){
long tmp = cf[term];
long new_num = tmp * num + den;
long new_den = num;
num = new_num;
den = new_den;
}
Fraction f;
f.num = num;
f.den = den;
f.val = (double)num / (double)den;
return f;
}
void get_fraction(double x){
System.out.println("x = " + x);
// Generate Continued Fraction
System.out.print("Continued Fraction: ");
double t = Math.abs(x);
double old_error = x;
Stack<long> cf;
Fraction f;
do{
// Get next term.
long tmp = (long)t;
cf.push(tmp);
// Build the current convergent
f = build_fraction(cf);
// Check error
double new_error = Math.abs(f.val - x);
if (tmp != 0 && new_error >= old_error){
// New error is bigger than old error.
// This means that the precision limit has been reached.
// Pop this (useless) term and break out.
cf.pop();
f = build_fraction(cf);
break;
}
old_error = new_error;
System.out.print(tmp + ", ");
// Error is zero. Break out.
if (new_error == 0)
break;
t -= tmp;
t = 1/t;
}while (cf.size() < 39); // At most 39 terms are needed for double-precision.
System.out.println();System.out.println();
// Print Results
System.out.println("The fraction is: " + f.num + " /" + f.den);
System.out.println("Target x = " + x);
System.out.println("Fraction = " + f.val);
System.out.println("Relative error is: " + (Math.abs(f.val - x) / x));System.out.println();
System.out.println();
}
public static void main(String[] args){
get_fraction(15.38 / 12.3);
get_fraction(0.3333333333333333333); // 1 /3
get_fraction(0.4184397163120567376); // 59 /141
get_fraction(0.8323518818409020299); // 1513686 /1818565
get_fraction(3.1415926535897932385); // pi
}
}
Eine WEITERE Sache:
Den oben genannten implementiert werden-dies funktioniert IN der THEORIE, jedoch aufgrund von floating-point-Rundungsfehler, diese Ergebnisse in eine Menge von unerwarteten Ausnahmen, Fehler-und Ausgänge. Unten ist eine praktische, robuste, aber ein bisschen schmutzig Umsetzung von Verhältnis-finding-Algorithmus (Javadoc würde für Ihre Bequemlichkeit):
public class RatioTest
{
/** Represents the radix point */
public static final char RAD_POI = '.';
/**
* Finds the ratio of the two inputs and returns that as a <tt>String</tt>
* <h4>Examples:</h4>
* <ul>
* <li><tt>getRatio(0.5, 12)</tt><ul>
* <li>returns "<tt>24:1</tt>"</li></ul></li>
* <li><tt>getRatio(3, 82.0625)</tt><ul>
* <li>returns "<tt>1313:48</tt>"</li></ul></li>
* </ul>
* @param d1 the first number of the ratio
* @param d2 the second number of the ratio
* @return the resulting ratio, in the format "<tt>X:Y</tt>"
*/
public static strictfp String getRatio(double d1, double d2)
{
while(Math.max(d1,d2) < Long.MAX_VALUE && (!Numbers.isCloseTo(d1,(long)d1) || !Numbers.isCloseTo(d2,(long)d2)))
{
d1 *= 10;
d2 *= 10;
}
long l1=(long)d1,l2=(long)d2;
try
{
l1 = (long)teaseUp(d1); l2 = (long)teaseUp(d2);
double gcd = getGCDRec(l1,l2);
return ((long)(d1 / gcd)) + ":" + ((long)(d2 / gcd));
}
catch(StackOverflowError er)
{
try
{
double gcd = getGCDItr(l1,l2);
return ((long)(d1 / gcd)) + ":" + ((long)(d2 / gcd));
}
catch (Throwable t)
{
return "Irrational ratio: " + l1 + " to " + l2;
}
}
}
/**
* <b>Recursively</b> finds the Greatest Common Denominator (GCD)
* @param i1 the first number to be compared to find the GCD
* @param i2 the second number to be compared to find the GCD
* @return the greatest common denominator of these two numbers
* @throws StackOverflowError if the method recurses to much
*/
public static long getGCDRec(long i1, long i2)
{
if (i1 == i2)
return i1;
if (i1 > i2)
return getGCDRec(i1 - i2, i2);
return getGCDRec(i1, i2 - i1);
}
/**
* <b>Iteratively</b> finds the Greatest Common Denominator (GCD)
* @param i1 the first number to be compared to find the GCD
* @param i2 the second number to be compared to find the GCD
* @return the greatest common denominator of these two numbers
*/
public static long getGCDItr(long i1, long i2)
{
for (short i=0; i < Short.MAX_VALUE && i1 != i2; i++)
{
while (i1 > i2)
i1 = i1 - i2;
while (i2 > i1)
i2 = i2 - i1;
}
return i1;
}
/**
* Calculates and returns whether <tt>d1</tt> is close to <tt>d2</tt>
* <h4>Examples:</h4>
* <ul>
* <li><tt>d1 == 5</tt>, <tt>d2 == 5</tt>
* <ul><li>returns <tt>true</tt></li></ul></li>
* <li><tt>d1 == 5.0001</tt>, <tt>d2 == 5</tt>
* <ul><li>returns <tt>true</tt></li></ul></li>
* <li><tt>d1 == 5</tt>, <tt>d2 == 5.0001</tt>
* <ul><li>returns <tt>true</tt></li></ul></li>
* <li><tt>d1 == 5.24999</tt>, <tt>d2 == 5.25</tt>
* <ul><li>returns <tt>true</tt></li></ul></li>
* <li><tt>d1 == 5.25</tt>, <tt>d2 == 5.24999</tt>
* <ul><li>returns <tt>true</tt></li></ul></li>
* <li><tt>d1 == 5</tt>, <tt>d2 == 5.1</tt>
* <ul><li>returns <tt>false</tt></li></ul></li>
* </ul>
* @param d1 the first number to compare for closeness
* @param d2 the second number to compare for closeness
* @return <tt>true</tt> if the two numbers are close, as judged by this method
*/
public static boolean isCloseTo(double d1, double d2)
{
if (d1 == d2)
return true;
double t;
String ds = Double.toString(d1);
if ((t = teaseUp(d1-1)) == d2 || (t = teaseUp(d2-1)) == d1)
return true;
return false;
}
/**
* continually increases the value of the last digit in <tt>d1</tt> until the length of the double changes
* @param d1
* @return
*/
public static double teaseUp(double d1)
{
String s = Double.toString(d1), o = s;
byte b;
for (byte c=0; Double.toString(extractDouble(s)).length() >= o.length() && c < 100; c++)
s = s.substring(0, s.length() - 1) + ((b = Byte.parseByte(Character.toString(s.charAt(s.length() - 1)))) == 9 ? 0 : b+1);
return extractDouble(s);
}
/**
* Works like Double.parseDouble, but ignores any extraneous characters. The first radix point (<tt>.</tt>) is the only one treated as such.<br/>
* <h4>Examples:</h4>
* <li><tt>extractDouble("123456.789")</tt> returns the double value of <tt>123456.789</tt></li>
* <li><tt>extractDouble("1qw2e3rty4uiop[5a'6.p7u8&9")</tt> returns the double value of <tt>123456.789</tt></li>
* <li><tt>extractDouble("123,456.7.8.9")</tt> returns the double value of <tt>123456.789</tt></li>
* <li><tt>extractDouble("I have $9,862.39 in the bank.")</tt> returns the double value of <tt>9862.39</tt></li>
* @param str The <tt>String</tt> from which to extract a <tt>double</tt>.
* @return the <tt>double</tt> that has been found within the string, if any.
* @throws NumberFormatException if <tt>str</tt> does not contain a digit between 0 and 9, inclusive.
*/
public static double extractDouble(String str) throws NumberFormatException
{
try
{
return Double.parseDouble(str);
}
finally
{
boolean r = true;
String d = "";
for (int i=0; i < str.length(); i++)
if (Character.isDigit(str.charAt(i)) || (str.charAt(i) == RAD_POI && r))
{
if (str.charAt(i) == RAD_POI && r)
r = false;
d += str.charAt(i);
}
try
{
return Double.parseDouble(d);
}
catch (NumberFormatException ex)
{
throw new NumberFormatException("The input string could not be parsed to a double: " + str);
}
}
}
}
- Konvertieren Sie beide Fraktionen, und dann Ausgabe, ratio (nach dem verkleinern)?
- und.... wie soll ich das tun?
- Ich habe gerade ersetzt, mein pseudo-code mit einer voll funktionsfähigen Implementierung in C++. Es sollte nicht zu schwer zu konvertieren, um Java.
- EDIT: ich habe gerade getestet mit meiner version besser. Es ist in der Lage, perfekt erkennen, die Fraktionen, die bei den meisten 4 - 5 Ziffern lang in beiden Zähler und Nenner. Etwas länger und es ist hit und miss. (Für die Java-version ändern Sie die
4294967296
zu2147483648
oder es könnte ein integer-überlauf bei der Besetzung.) - Für Ihren aktualisierten code, Skalierung von
2
statt10
wird loszuwerden, die Rundungsfehler. Aber es gibt verschiedene (aber immer noch gültigen) Antworten. Meine Umsetzung leidet auch stark von round-off. (also, warum es nicht funktioniert, wenn der Anteil größer ist als 5 Ziffern.) Es gibt einen Weg, um dieses Problem zu lösen, aber es ist auch messier... - Gute Idee - ich werde das ausprobieren!
Du musst angemeldet sein, um einen Kommentar abzugeben.
Vorausgesetzt, Sie haben einen Datentyp und kann mit beliebig großen numerischen Werten, die Sie tun können, so etwas wie dieses:
So für Sie Beispiel müssten Sie so etwas wie dieses:
1/3
wenn es das ist, was die gewünschte Antwort ist.Dies ist ein ziemlich nicht-trivial. Der beste Ansatz, ich weiß, die gibt zuverlässige Ergebnisse für zwei floating-point ist die Verwendung kettenbrüche.
Erste, teilen Sie die zwei zahlen, um die Quote in floating-point. Dann laufen die weiter fraction-Algorithmus, bis er beendet wird. Wenn es nicht beenden, dann ist es irrational und es gibt keine Lösung.
Wenn es beendet wird, bewerten das daraus resultierende fortgesetzte Bruch zurück in eine einzige Fraktion, und das wird die Antwort sein.
Natürlich, es gibt keine zuverlässige Methode um festzustellen, ob es eine Lösung gibt oder nicht, da dies wird das Halteproblem. Aber für die Zwecke beschränkt precision floating-point, wenn die Sequenz nicht beenden, mit einer angemessenen Anzahl von Schritten, dann übernehmen es gibt keine Antwort.
EDIT 2:
Hier ein update zu meinem ursprünglichen Lösung in C++. Diese version ist viel stabiler und scheint zu funktionieren, jede positive floating-point-Zahl, außer für
INF
,NAN
oder extrem große oder kleine Werte, würde ein integer-überlauf.Ausgabe:
Die Sache, hier zu bemerken ist, dass es gibt
245850922 /78256779
fürpi
. Offensichtlich pi irrational ist. Aber so weit wie die doppelte Genauigkeit ermöglicht es, die245850922 /78256779
ist nichts anderespi
.Grundsätzlich jede Fraktion mit 8 - 9 Ziffern im Zähler/Nenner hat genug Entropie zur Abdeckung fast aller DP-floating-point-Werte (abgesehen von Sonderfällen wie
INF
,NAN
oder sehr große/kleine Werte).6/13
in deinem Beispiel, die Fortsetzung der Bruchteil Sequenz wird sehr kurz sein: für6/13
es ist [0, 2, 6], die nur 3 Bedingungen.INFINITY
,NEGATIVE_INFINITY
oderNaN
. Auch gibt es nicht immer einen rationalen Bruchteil für zwei Dezimalzahlen. Was die pi-Werte über 7, zum Beispiel?Wenn die floating-point-zahlen haben eine Begrenzung auf dezimal stellen - dann einfach multiplizieren Sie beide zahlen durch 10^n, wo n ist begrenzt - also für 2 Dezimalstellen, multipliziert mit 100, dann berechnen Sie für ganze zahlen - das Verhältnis wird das gleiche für die ursprüngliche Dezimalzahlen, denn es ist ein Verhältnis.
1.0
und0.333333333333333
. Diese Methode der Skalierung von 10 geben nur einen Bruchteil der "333333333333333 / 1000000000000000'. Aber diese Methode gibt dir nicht1/3
, wenn es das ist, was Sie sich wünschen.In der Maxima CAS einfach :
Code aus zahlen.lisp :
Bin ich mit dem folgenden Algorithmus. Es ist schnell und einfach. Es nutzt die Tatsache, dass 10^N = 2^N * 5^N und es kann auch mit wiederkehrenden mustern der Ziffern ! Ich hoffe es wird Euch helfen.
Bruch-zu-ratio-Konverter
Einige demos sind auch auf dieser Seite.