例如，如果我的函数被调用getlowestfraction()，这就是我期望它做的事情：
getlowestfraction(0.5) // returns 1, 2 or something along the lines of that
另一个例子：
getlowestfraction(0.125) // returns 1, 8 or something along the lines of that
问问题
3185 次
6 回答
13
使用连分数可以有效地创建一个（有限或无限）分数序列h n /k n，它们是给定实数x的任意良好近似。
如果x是有理数，则该过程在h n /k n == x的某个点处停止。如果x不是有理数，则序列h n /k n , n = 0, 1, 2, ...会很快收敛到x 。
连分数算法只产生约化分数（分母和分母互质），分数在某种意义上是给定实数的“最佳有理近似值”。
我不是 JavaScript 人（通常用 C 编程），但我尝试使用以下 JavaScript 函数来实现该算法。如果有愚蠢的错误，请原谅我。但我已经检查了该功能，它似乎工作正常。
function getlowestfraction(x0) {
var eps = 1.0E-15;
var h, h1, h2, k, k1, k2, a, x;
x = x0;
a = Math.floor(x);
h1 = 1;
k1 = 0;
h = a;
k = 1;
while (x-a > eps*k*k) {
x = 1/(x-a);
a = Math.floor(x);
h2 = h1; h1 = h;
k2 = k1; k1 = k;
h = h2 + a*h1;
k = k2 + a*k1;
}
return h + "/" + k;
}
当有理逼近精确或具有给定精度时，循环停止eps = 1.0E-15。当然，您可以根据需要调整精度。（该while条件源自连分数理论。）
示例（带有 while 循环的迭代次数）：
getlowestfraction(0.5) = 1/2 (1 iteration)
getlowestfraction(0.125) = 1/8 (1 iteration)
getlowestfraction(0.1+0.2) = 3/10 (2 iterations)
getlowestfraction(1.0/3.0) = 1/3 (1 iteration)
getlowestfraction(Math.PI) = 80143857/25510582 (12 iterations)
请注意，该算法给出了1/3的近似值x = 1.0/3.0。重复乘以x10 的幂并取消公因数会得到类似3333333333/10000000000.
以下是不同精度的示例：
- 随
eps = 1.0E-15你得到getlowestfraction(0.142857) = 142857/1000000。 - 随
eps = 1.0E-6你得到getlowestfraction(0.142857) = 1/7。
于 2012-12-23T13:23:10.350 回答
1
您可以继续乘以十，直到您的分子和分母具有整数值，然后使用此问题的答案将分数简化为最简单的项。
于 2012-12-22T11:01:11.123 回答
1
试试这个程序：
function toFrac(number) {
var fractional = number % 1;
if (fractional) {
var real = number - fractional;
var exponent = String(fractional).length - 2;
var denominator = Math.pow(10, exponent);
var mantissa = fractional * denominator;
var numerator = real * denominator + mantissa;
var gcd = GCD(numerator, denominator);
denominator /= gcd;
numerator /= gcd;
return [numerator, denominator];
} else return [number, 1];
}
function gcd(numerator, denominator) {
do {
var modulus = numerator % denominator;
numerator = denominator;
denominator = modulus;
} while (modulus);
return numerator;
}
然后你可以按如下方式使用它：
var start = new Date;
var PI = toFrac(Math.PI);
var end = new Date;
alert(PI);
alert(PI[0] / PI[1]);
alert(end - start + " ms");
你可以在这里看到演示：http: //jsfiddle.net/MZaK9/1/
于 2012-12-22T11:40:18.817 回答
0
只是摆弄代码，自己得到了答案：
function getlowestfraction (num) {
var i = 1;
var mynum = num;
var retnum = 0;
while (true) {
if (mynum * i % 1 == 0) {
retnum = mynum * i;
break;
}
// For exceptions, tuned down MAX value a bit
if (i > 9000000000000000) {
return false;
}
i++;
}
return retnum + ", " + i;
}
以防有人需要。
PS：我不是想展示我的专业知识或知识范围。实际上，我确实在 JSFiddle 中花了很长时间试图弄清楚这一点（无论如何也不是很长时间）。
于 2012-12-22T10:55:02.787 回答
0
假设数字是x = 0 . ( a_1 a_2 ... a_k ) ( a_1 a_2 ... a_k ) ....为了简单起见（请记住，前几位数字可能不符合重复模式，我们需要一种方法来弄清楚是什么k）。如果b是基数，那么
b ^ k * x - x = ( b ^ k - 1 ) * x
一方面，但
b ^ k * x - x = ( a_1 a_2 ... a_k )
（确切地说，即这是一个整数）另一方面。
所以
x = ( a_1 ... a_k ) / ( b ^ k - 1 )
现在您可以使用欧几里得算法得到 gcd 并将其除以得到减少的分数。
您仍然需要弄清楚如何确定重复序列。这个问题应该有答案。\1编辑 - 一个答案：它是如果与模式匹配的长度/([0-9]+)\1+$/（您可能想在匹配 bc 的舍入之前丢弃最后一个数字）。如果没有匹配，那么没有比“平凡”表示更好的“答案”了（x*base^precision/base^precision）。
注意这个答案对您对答案的期望做出了一些假设，可能不适合您的需求。但这是从重复的十进制表示中复制分数的“教科书”方式 -参见例如here
于 2012-12-23T07:37:37.557 回答
0
一个非常古老但又是黄金的问题，同时也是一个被忽视的问题。所以我会去把这个受欢迎的标记为重复，希望新人最终会出现在正确的地方。
这个问题的公认答案是互联网的瑰宝。我所知道的任何图书馆都没有使用这种宏伟的技术，最终得出的结果不是错误的而是愚蠢的理性。话虽如此，由于以下几个问题，公认的答案并不完全正确；
- 那里到底发生了什么？
- 为什么它仍然返回
'140316103787451/7931944815571'而不是'1769/100'输入时返回17.69？ - 你如何决定何时停止
while循环？
现在最重要的问题是，那里发生了什么以及该算法为何如此高效。
我们必须知道，任何数字也可以表示为连续分数。说给你0.5。你可以这样表达
1
0 + ___ // the 0 here is in fact Math.floor(0.5)
2 // the 2 here is in fact Math.floor(1/0.5)
所以说你得到了2.175然后你最终得到
1
2 + _______________ // the 2 here is in fact Math.floor(2.175)
1
5 + ___________ // the 5 here is in fact Math.floor(1/0.175 = 5.714285714285714)
1
1 + _______ // the 1 here is in fact Math.floor(1/0.714285714285714 = 1.4)
1
2 + ___ // the 2 here is in fact Math.floor(1/0.4 = 2.5)
2 // the 2 here is in fact Math.floor(1/0.5)
我们现在有了像[2;5,1,2,2]for一样的连分数系数2.175。然而，这个算法的美妙之处在于它如何在我们计算下一个连分数常数时立即计算近似值，而不需要任何进一步的计算。此时，我们可以将当前达到的结果与给定值进行比较，并决定停止或再次迭代。
到目前为止这么好，但它仍然没有意义，对吧？让我们举另一个可靠的例子。输入值为3.686635944700461。现在我们将处理这个问题Infinity并很快收敛到结果。所以我们的第一个理性是1/0aka Infinity。我们将其表示为分子n0为1分母d0为0aka的分数1/0。第二个近似值将是积分部分，即是这样，3然后我们需要一个中间结果，就像下一阶段一样。让我们开始吧。也是如此。_ _n13d11n2/d20n20d21
重要的部分是，一旦我们知道了前两个近似值 ( n0,和) d0，我们就可以计算下一个系数以及下一个近似值，也就是与输入进行比较。计算系数就像下一个浮动部分的倒数一样简单。然后近似值将是。（定理 2.4 @本文）n1d1n2d2iMath.floor(xn)xnn2/d2(i * n1 + n0)/(i * d1 + d0)
现在给出上述信息，任何体面的程序员都可以轻松解决以下代码段。好奇的3.686635944700461是800/217，下面的代码只需要 5 次迭代就可以计算出来。
function toRational(x){
var i = Math.floor(x),
xn = 1/(x-i),
n0 = 1,
d0 = 0,
n1 = i,
d1 = 1,
n2 = 0,
d2 = 1;
if (x === i) return {n:n1,d:d1};
while (Math.abs(x - n1/d1) > Number.EPSILON){
i = Math.floor(xn);
n2 = i * n1 + n0;
d2 = i * d1 + d0;
n0 = n1;
d0 = d1;
n1 = n2;
d1 = d2;
xn = 1/(xn-i);
}
return isNaN(x) ? NaN : {n:n1,d:d1};
}
在实际考虑中，最好将系数存储在分数对象中，以便将来您可以使用它们在有理数之间执行 CFA（连续分数算术）。这样，您可以BigInt通过留在 CF 域中执行求逆、求反、加法和乘法运算来避免巨大的整数和可能的使用。遗憾的是，CFA 是一个非常容易被忽视的话题，但它可以帮助我们在对有理类型值进行级联算术运算时避免双精度错误。
于 2022-02-17T20:18:37.677 回答