算法确定两个浮点数的比例是多少? [英] Algorithm for finding the ratio of two floating-point numbers?
问题描述
我需要找到一个浮点数另一比,和该比需要是两个整数。例如:
- 输入:
1.5,3.25
- 输出:
6:13
有谁知道一个?搜索互联网,我没有发现这样的算法,也不是算法最小公倍数或两个分母浮点数(只是整数)。
Java实现的:
这是最后的实现,我会用:
公共类RatioTest
{
公共静态字符串getRatio(双D1,D2双)// 1.5,3.25
{
而(Math.max(D1,D2)<为Long.MAX_VALUE和放大器;&安培; D1 =(长)D1和放大器;!&安培; D2 =(长)D2!)
{
D1 * = 10; // 15 - > 150
D2 * = 10; // 32.5 - > 325
}
// D1 = = 150.0
// D2 = = 325.0
尝试
{
双最大公约数= getGCD(D1,D2); //最大公约数== 25
返程((长)(D1 / GCD))+:+((长)(D2 / GCD)); //6:13
}
赶上(的StackOverflowError ER)//如果getGDC(递归循环法)重复次数过多
{
抛出新ArithmeticException(非理性比+ D1 +到+ D2);
}
}
公共静态双getGCD(双I1,I2双)//(150325) - > (150175) - > (150,25) - > (125,25) - > (100,25) - > (75,25) - > (50,25) - > (25,25)
{
如果(I1 = = I2)
返回I1; // 25
如果(I1> I2)
返回getGCD(i1的 - I2,I2); //(125,25) - > (100,25) - > (75,25) - > (50,25) - > (25,25)
返回getGCD(I1,I2 - 的i1); //(150175) - > (150,25)
}
}
-
- >
表示下一阶段的循环或方法调用
神秘的实现,Java的:
虽然我用这个并没有结束,它比应该得到认可,所以我把它翻译成Java,所以我能理解:
进口java.util.Stack中;
公共类RatioTest
{
类分数{
长NUM;
长登;
双VAL;
};
分数build_fraction(堆栈<长> CF){
长期= cf.size();
长NUM = CF [名词 - 1];
长登= 1;
而(term--大于0){
长TMP = CF [任期]
长new_num = TMP * NUM +书房;
长new_den = NUM;
NUM = new_num;
书房= new_den;
}
分数f;
f.num = NUM;
f.den =巢穴;
f.val =(双)NUM /(双)巢穴;
返回F;
}
无效get_fraction(双X){
的System.out.println(×=+ x)的;
//生成连分数
System.out.print(连分数:);
双T = Math.abs(X);
双old_error = X;
堆叠<长>比照;
分数f;
做{
//获取下学期。
长TMP =(长)吨;
cf.push(TMP);
//创建当前收敛
F = build_fraction(CF);
//检查错误
双new_error = Math.abs(f.val - X);
如果(TMP = 0&放大器;!&安培; new_error> = old_error){
//新误差大于旧的错误。
//这意味着,precision限制已经达到。
//弹出这个(没用)项和爆发。
cf.pop();
F = build_fraction(CF);
打破;
}
old_error = new_error;
System.out.print(TMP +,);
//误差为零。爆发。
如果(new_error == 0)
打破;
笔 - = TMP;
吨= 1 /吨;
}而(cf.size()< 39);都需要双precision //最多39项。
的System.out.println();的System.out.println();
//打印结果
的System.out.println(分数是:+ f.num +/+ f.den);
的System.out.println(靶X =+ x)的;
的System.out.println(分数=+ f.val);
的System.out.println(相对误差是:+(Math.abs(f.val - X)/ X));的System.out.println();
的System.out.println();
}
公共静态无效的主要(字串[] args){
get_fraction(15.38 / 12.3);
get_fraction(0.3333333333333333333); //三分之一
get_fraction(0.4184397163120567376); //一百四十一分之五十九
get_fraction(0.8323518818409020299); //一百八十一万八千五百六十五分之一百五十一万三千六百八十六
get_fraction(3.1415926535897932385); // PI
}
}
一件事:
这样做的上述实施方式的工作原理,理论,但由于浮点舍入误差,这将导致无法预料的异常,错误和产出很多。下面是一个比寻找算法(Javadoc'd为了您的方便)的实用,强劲,但有点脏的实现:
公共类RatioTest
{
/ **重新presents小数点* /
公共静态最后的char RAD_POI ='';
/ **
*查找的两个输入之比,并返回作为&其中; TT>字符串&所述; / TT>
*< H4>的例子:其中,/ H4>
*< UL>
*<李>< TT> getRatio(0.5,12)< / TT>< UL>
*<李>返回< TT> 24:1< / TT>< /李>< / UL>< /李>
*<李>< TT> getRatio(3 82.0625)LT; / TT>< UL>
*<李>返回< TT> 1313:48< / TT>< /李>< / UL>< /李>
*< / UL>
* @参数D1之比的第一数目
* @参数d2的比值的第二数目
返回:得到的比例,其格式为< TT> X:Y< / TT>中
* /
公共静态strictfp字符串getRatio(双D1,D2的双)
{
而(Math.max(D1,D2)<为Long.MAX_VALUE和放大器;&安培;!(Numbers.isCloseTo(D1,(长)D1)|| Numbers.isCloseTo(D2,(长)D2)))
{
D1 * = 10;
D2 * = 10;
}
长L1 =(长)D1,L2 =(长)D2;
尝试
{
L1 =(长)teaseUp(D1); L2 =(长)teaseUp(D2);
双最大公约数= getGCDRec(L1,L2);
返回((长)(D1 / GCD))+:+((长)(D2 / GCD));
}
赶上(的StackOverflowError ER)
{
尝试
{
双最大公约数= getGCDItr(L1,L2);
返回((长)(D1 / GCD))+:+((长)(D2 / GCD));
}
捕获(的Throwable T)
{
回到非理性比+ L1 +到+ 12;
}
}
}
/ **
*< B>递归< / B>找到最大公约数(GCD)
*参数I1第一个数字做个比较,发现GCD
* @参数I2的第二数量进行比较,以找到GCD
返回:这两个数的最大公分母
* @throws的StackOverflowError如果该方法递归得多
* /
公共静态长getGCDRec(长I1,I2长)
{
如果(I1 = = I2)
返回I1;
如果(I1> I2)
返回getGCDRec(I1 - I2,I2);
返回getGCDRec(I1,I2 - 的i1);
}
/ **
*< B>迭代< / B>找到最大公约数(GCD)
*参数I1第一个数字做个比较,发现GCD
* @参数I2的第二数量进行比较,以找到GCD
返回:这两个数的最大公分母
* /
公共静态长getGCDItr(长I1,I2长)
{
对于(简称I = 0; I< Short.MAX_VALUE和放大器;&安培; I1 = I2;!我++)
{
而(I1> I2)
I1 = I1 - I2;
而(I2> I1)
I2 = I2 - I1;
}
返回I1;
}
/ **
*计算并返回是否< TT> D1< / TT>接近到< TT> D2< / TT>
*< H4>的例子:其中,/ H4>
*< UL>
*<李>< TT> D1 = = 5℃/ TT&GT中,< TT> D2 == 5℃/ TT>
*< UL><李>返回< TT>真< / TT>< /李>< / UL>< /李>
*<李>< TT> D1 = = 5.0001< / TT&GT中,< TT> D2 == 5℃/ TT>
*< UL><李>返回< TT>真< / TT>< /李>< / UL>< /李>
*<李>< TT> D1 = = 5℃/ TT&GT中,< TT> D2 = = 5.0001< / TT>
*< UL><李>返回< TT>真< / TT>< /李>< / UL>< /李>
*<李>< TT> D1 = = 5.24999< / TT&GT中,< TT> D2 == 5.25< / TT>
*< UL><李>返回< TT>真< / TT>< /李>< / UL>< /李>
*<李>< TT> D1 = = 5.25< / TT&GT中,< TT> D2 = = 5.24999< / TT>
*< UL><李>返回< TT>真< / TT>< /李>< / UL>< /李>
*<李>< TT> D1 = = 5℃/ TT&GT中,< TT> D2 == 5.1< / TT>
*< UL><李>返回< TT>假< / TT>< /李>< / UL>< /李>
*< / UL>
*参数D1的第一个数字来比较亲密
*参数D2的第二个数字来比较亲密
* @返回< TT>真< / TT>如果两个数接近,作为判断由该方法
* /
公共静态布尔isCloseTo(双D1,D2的双)
{
如果(D1 == D2)
返回true;
双T;
串的ds = Double.toString(d1)的;
如果((T = teaseUp(D1-1))== || D2(T = teaseUp(D2-1))== D1)
返回true;
返回false;
}
/ **
*不断增加的最后一位数字的与&lt值; TT> D1&所述; / TT>直到的双重长度变化
* @参数D1
* @返回
* /
公共静态双teaseUp(双D1)
{
字符串s = Double.toString(D1),O = S;
BYTE B;
对于(字节C = 0; Double.toString(extractDouble(S))长()> = 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);
返回extractDouble(多个);
}
/ **
*工程就像Double.parseDouble,但忽略任何多余的字符。第一个小数点(小于TT>< / TT>)的唯一一个如此对待< BR />
*< H4>的例子:其中,/ H4>
*<李>< TT> extractDouble(123456.789)< / TT>返回&LT的双重价值; TT> 123456.789< / TT>< /李>
*<李>< TT> extractDouble(1qw2e3rty4uiop [5a'6.p7u8和9)< / TT>返回&LT的双重价值; TT> 123456.789< / TT>< /李>
*<李>< TT> extractDouble(123,456.7.8.9)< / TT>返回&LT的双重价值; TT> 123456.789< / TT>< /李>
*<李>< TT> extractDouble(我有$ 9,862.39在银行。)LT; / TT>返回&LT的双重价值; TT> 9862.39< / TT>< /李>
*参数海峡的< TT>字符串< / TT>从中提取< TT>双< / TT取代。
返回:在< TT>双< / TT>已在字符串中发现,如果有的话。
* @throws NumberFormatException异常,如果< TT> STR< / TT>不包含0和9之间,包容一个数字。
* /
公共静态双extractDouble(字符串str)抛出NumberFormatException异常
{
尝试
{
返回Double.parseDouble(STR);
}
最后
{
布尔R =真;
字符串D =;
的for(int i = 0; I< str.length();我++)
如果(Character.isDigit(str.charAt(ⅰ))||(str.charAt(ⅰ)== RAD_POI&安培;&安培; r)的)
{
如果(str.charAt(ⅰ)== RAD_POI&安培;&安培; r)的
R = FALSE;
D + = str.charAt(ⅰ);
}
尝试
{
返回Double.parseDouble(四);
}
赶上(NumberFormatException的前)
{
抛出新NumberFormatException的(输入字符串不能解析为双:+ STR);
}
}
}
}
假设你有一个能够处理任意大数值的数据类型,你可以做这样的事情:
- 乘以10这两个值,直至尾数是完全小数点的左侧。
- 找到两个值的最大公约数。
- 在除以GCD
所以,你比如你有这样的事情:
A = 1.5 B = 3.25 乘以10:15,32.5 乘以10:150,325 发现GCD:25 除以GCD:6,13
I need to find the ratio of one floating-point number to another, and the ratio needs to be two integers. For example:
- input:
1.5, 3.25
- output:
"6:13"
Does anyone know of one? Searching the internet, I found no such algorithm, nor an algorithm for the least common multiple or denominator of two floating-point numbers (just integers).
Java implementation:
This is the final implementation that I will use:
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)
}
}
->
indicates the next stage in the loop or method call
Mystical's implementation as Java:
Though I did not end up using this, it more than deserves to be recognized, so I translated it to Java, so I could understand it:
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
}
}
One MORE thing:
The above mentioned implemented way of doing this works IN THEORY, however, due to floating-point rounding errors, this results in alot of unexpected exceptions, errors, and outputs. Below is a practical, robust, but a bit dirty implementation of a ratio-finding algorithm (Javadoc'd for your convenience):
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);
}
}
}
}
Assuming you have a data type that can handle arbitrarily large numeric values, you can do something like this:
- Multiply both values by 10 until the significand is entirely to the left of the decimal point.
- Find the Greatest Common Denominator of the two values.
- Divide by GCD
So for you example you would have something like this:
a = 1.5 b = 3.25 multiply by 10: 15, 32.5 multiply by 10: 150, 325 find GCD: 25 divide by GCD: 6, 13
这篇关于算法确定两个浮点数的比例是多少?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!