运行 执行...计算直到满足条件
Run Do...While Calculations Until Condition Is Met
我正在使用 Javascript 编写一个简单的 do...while 语句，目的是查看给定输入 num 的小数点长度，以及小数点的长度是否更大大于或等于 1，取 num 并将其添加到自身上，直到十进制长度等于 0。目前，它适用于长度为 1 的小数，但任何更大的，它都会停止。
预期的输出，例如当num为8.75时，应该是35，而不是17.5。
该系列应该需要 4 个步骤才能达到 35。
8.75
17.5
26.25
35
这是我的代码：
const num = 8.75;
var decimalLength = num.toString().split(".")[1].length;
let result = "";
let i = num;
do {
i = i + num;
result = result + num;
newLength = decimalLength;
} while (newLength < 0);
console.log(i);
您可以使用一些奇特的数学来获得不会一遍又一遍地循环的更明确的答案：
const num = 8.75;
var decimal = num % 1 //Decimal part
var decimalPlaces = num.toString().split(".")[1] ?.length || 0; //Get decimal places
//GCD function
const gcd = (x, y) => (!y ? x : gcd(y, x % y));
//GCD between decimal and 1, need to make it whole number to get multiplier, so multiply each with 10^[decimal places]
//Get what's remaining when divided by 10^[decimal places] as well, to see what to multiply by to get whole number
var multiplier = 10 ** decimalPlaces / gcd(10 ** decimalPlaces, decimal * 10 ** decimalPlaces)
//Use log change of base property to get value in power of 2
var outputExponent = Math.log(multiplier) / Math.log(2)
//Multiply number by multiplier
var outputValue = num * multiplier
console.log(outputExponent) //Power of 2 to multiply by to get whole number
console.log(outputValue) //The whole number itself
此版本使用递归函数和容差来处理浮点舍入错误。
const firstIntMultiple = (n, tol=1e-6, c = 1) =>
Math.abs(n * c - Math.floor(n * c)) < tol ? n * c : firstIntMultiple (n, tol, c + 1)
console .log (firstIntMultiple (8.75)) // 35/4
console .log (firstIntMultiple (8.333333333333334)) // 25/3
console .log (firstIntMultiple (14.058823529411764)) // 239/17
它通过乘以连续的整数而不是连续的加法来找到正确的版本，但它的想法是一样的。
我们可以很容易地用迭代方法替换递归版本，这对于没有很好的有理逼近的数字可能很有用。 （现在，传递 Math.PI 将 运行 进入递归限制。）
可能看起来像这样：
const firstIntMultiple = (n, tol=1e-6) => {
let c = 1;
while (Math.abs(n * c - Math.floor(n * c)) > tol) {
c += 1
}
return n * c
}
而对于 Math.PI，那将是 return 4272943.0000005495，整数 1e-6 范围内的第一个圆周率倍数。您可以根据需要调整公差。
更新 -- 一种完全不同的技术
另一种技术将利用 the fact that continued fractions 提供一种直接的方法来找到数字的最佳有理近似值。我们可以使用它来找到 pi 的十个最佳有理近似值，例如：
bestApprox (Math.PI, 1, 10) .map (({n, d}) => `${n}/${d}`)
// => ["3/1", "22/7", "333/106", "355/113", "103993/33102", "104348/33215",
// "208341/66317", "312689/99532", "833719/265381", "1146408/364913"]
然后，使用这些近似值，我们可以找到第一个与我们的目标值相距不远的值。
代码可能如下所示：
const contFrac = (n, d = 1, count = Infinity) =>
count < 1 || d == 0
? []
: [Math .floor (n / d)] .concat (contFrac (d, n % d, count - 1))
const bestApprox = (n, d = 1, c) =>
contFrac(n, d, c)
.reduce ((a, n, i) => [
...a,
{
n: a [i] .n + n * a [i + 1] .n,
d: a [i] .d + n * a [i + 1] .d
}
], [{n: 0, d: 1}, {n: 1, d: 0}])
.slice (2)
const firstIntMultiple = (x, ε = 1e-6) =>
bestApprox (x, 1)
.find (({n, d}, i, a) => i == a.length - 1 || Math.abs (n / d - x) < ε)
.n
console .log (firstIntMultiple (8.75)) // 35/4
console .log (firstIntMultiple (8.333333333333334)) // 25/3
console .log (firstIntMultiple (14.058823529411764)) // 239/17
console .log (firstIntMultiple (Math.PI)) // 353/113
console .log (firstIntMultiple (Math.PI, 1e-8)) // 103993/33102
我没有测试性能，但这应该相当不错，尤其是对于那些连分数早期包含大整数的数字。 （例如 pi 是 <3; 7, 15, 1, 292,...> 那 292 意味着 3 + (1 / (7 + (1 / (15 + 1 / 1)))) 或 355 / 113 是 pi 的极好近似值，事实上，它很好精确到小数点后六位。
我不知道这对 OP 有多大帮助，但它表明古老的数学 类 可能有一天会派上用场！。 ;-)
更新 2 - 现在有更多解释！
此版本通过检查测试值是否在原始值的 epsilon 范围内而不检查测试值的 ratio 来解决使用小值的第二种方法中的问题原始值的测试值在 1 的 epsilon 范围内。它也有一些小的清理和默认 epsilon 的较小值：
const contFrac = (n, d = 1, count = Infinity) =>
count < 1 || d == 0
? []
: [Math .floor (n / d)] .concat (contFrac (d, n % d, count - 1))
const bestApprox = (n, d = 1, count = Infinity) =>
contFrac(n, d, count)
.reduce ((a, n, i) => [
...a,
{
n: a [i] .n + n * a [i + 1] .n,
d: a [i] .d + n * a [i + 1] .d
}
], [{n: 0, d: 1}, {n: 1, d: 0}])
.slice (2)
const isClose = (x, y, ε) =>
y == 0 ? x < ε : (x / y > 1 - ε && x / y < 1 + ε)
const firstIntMultiple = (x, ε = 1e-8) =>
bestApprox (x, 1)
.find (({n, d}, i, a) => i == a.length - 1 || isClose (n / d, x, ε))
.n
console .log (firstIntMultiple (8.75)) // 35/4
console .log (firstIntMultiple (8.333333333333334)) // 25/3
console .log (firstIntMultiple (14.058823529411764)) // 239/17
console .log (firstIntMultiple (Math.PI)) // 103993/33102
console .log (firstIntMultiple (Math.PI, 1e-6)) // 353/113
console .log (firstIntMultiple (13.000000221)) // 58823532/4524887
console .log (firstIntMultiple (1.0000003333)) // 3000301/3000300
console .log (firstIntMultiple (1234/987654321)) // 6/4802209
.as-console-wrapper {min-height: 100% !important; top: 0}
说明
这里主要的功能还是firstIntMultiple，而且比较简单，就是搜索bestApprox的结果，找一个和我们目标数足够接近的有理逼近，然后returning 该结果的分子。 “足够接近”由 isClose 确定，它检查两个数字的比率是否在 1 - ε 和 1 + ε 之间，其中 ε 是一个可选参数，默认为 1e-8.
所以问题是 bestApprox 是如何工作的。为此，我们需要讨论 Continued Fractions。我不能在这里公正地对待他们，但希望我能描述得足够多，让他们对他们有所了解。
这是一个重复的无限简单连分数：
1
1 + ---------------------------------
1
2 + ----------------------------
1
2 + ---------------------
1
2 + ---------------
1
2 + ---------
2 + ...
这是一个连分数，因为我们在其他分数的分母中保留嵌套分数。它是无限的，因为……好吧，因为它会无限地继续——以一种显而易见的方式。这很简单，因为所有
分子是 1s.
不难用一点代数证明这代表 2.
的平方根
这通常会缩写为这样的符号：
<1; 2, 2, 2, 2, ...>
其中所有值都是整数，第一个之后都是正值。
这些有一些优点。所有有理数都有一个有限的连分数表示，所有二次数都有一个重复的无限模式。但更重要的是，这些连分数的前缀包含对数字的最佳有理逼近。 （证明不是特别难，应该是非数学家也能看懂的，不过这里就不试了。）
我的意思是这些数字：
<1;> //=> 1
<1; 2> //=> 3/2
<1; 2, 2> //=> 7/5
<1; 2, 2, 2> //=> 17/12
<1; 2, 2, 2, 2> //=> 41/29
...
是 sqrt(2) 的连续更好的近似值，除了更高的分母，没有更好的近似值可用。也就是说，例如，在大于 12 和小于 29 的分母中，没有比 sqrt(2).
更好的近似值
因此，通过计算一个数的部分连分数，我们可以找到所有最佳近似值，并最终找到一个能够得到我们正在寻找的倍数的近似值。
现在我们需要知道如何计算这些连分数，然后如何将它们的分式变成有理数。幸运的是，两者都很简单。
要找到连分数的元素，我们需要做的就是找到数字的下限，将其添加到我们的列表中，然后继续计算余数的倒数。
如果我们从 27/11 开始，那么第一个元素将是 floor(27/11) 或 2；余数是 5/11，它是 11/5 的倒数，下一位是它的底数，即 2，余数是 1/5，它的倒数是 5 没有余数。所以 27/11 可以写成 <2; 2, 5>.
如果我们从 pi 开始，那么我们的第一个元素将是 3，然后我们将继续 0.14159265358979312 的倒数，即 7.062513305931052，下一个元素将是 7。取余数的倒数，得到15.996594406684103，下一个元素为15。该余数的倒数是 1.0034172310150002，因此下一个元素是 1。然后余数的倒数变得更大，达到 292.63459087501246。我们可以继续得到这样的结果：
<3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 3, 3, 2, 1, ...>
没有明显的规律。但是 292 的高值告诉我们 <3; 7, 15, 1> 或 355/113 是 pi.
的极好近似值
函数 contFrac 按照描述执行此算法。
现在，要将偏数转换为有理数，我们可以使用简单的递归。在<a_0; a_1, a_2, a_3, ...>中，第一个近似值是a_0，我们写成a_0/1。第二个是 a_0 + (1 / a_1) 或 (a_0 * a_1) / a_1。之后，我们可以通过以下简单公式找到第 (k + 2) 个值：n_(k + 2) = a_(k + 2) * n_(k + 1) + n_k 和 d_(k + 2) = a_(k + 2) * d_(k + 1) + d_k.
所以对于 <3; 7, 15, 1>，我们从 3/1 开始，然后是 22/7，然后我们的下一个值是 (15 * 22 + 3) / (15 * 7 + 1) 或 333/106，然后是 (1 * 333 + 22) / (1 * 106 + 7) 或 355/113。该代码使用了一个小技巧，将分子和分母向后扩展了两步，这样我们就可以对每一步都使用递归，然后简单地将这两个值从最终结果中切出。
我们已经有了。通过对一个数使用最好的有理近似值，我们可以快速找到最小的整数，在很小的公差范围内，它是该数的倍数。
两个相互矛盾的答案。哪个更好？在你测试之前没有办法知道。所以，这就是这个新答案试图做的。
这些 'tests'（如果你愿意）运行 每个函数 50 次，在清除控制台和记录时间平均值之前对每次迭代进行计时。
8 位小数精度
Endothermic_Dragon:
const num = 3.14159265;
//Function start
const firstIntMultiple = () => {
var decimal = num % 1;
var decimalPlaces = num.toString().split(".")[1] ?.length || 0;
const gcd = (x, y) => (!y ? x : gcd(y, x % y));
var multiplier = 10 ** decimalPlaces / gcd(10 ** decimalPlaces, decimal * (10 ** decimalPlaces));
return num * multiplier;
}
//Function end
var times = []
for (var i = 0; i < 50; i++) {
var startTime = new Date()
console.log(firstIntMultiple().toString())
times.push((new Date() - startTime) / 1000)
}
console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")
斯科特·萨耶特：
const num = 3.14159265;
//Function start
const firstIntMultiple = (tol = 1e-8) => {
let c = 1;
while (Math.abs(num * c - Math.floor(num * c)) > tol) {
c += 1
}
return num * c
}
//Function end
var times = []
for (var i = 0; i < 50; i++) {
var startTime = new Date()
console.log(firstIntMultiple().toString())
times.push((new Date() - startTime) / 1000)
}
console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")
10 进制精度
Endothermic_Dragon:
const num = 3.1415926535;
//Function start
const firstIntMultiple = () => {
var decimal = num % 1;
var decimalPlaces = num.toString().split(".")[1] ?.length || 0;
const gcd = (x, y) => (!y ? x : gcd(y, x % y));
var multiplier = 10 ** decimalPlaces / gcd(10 ** decimalPlaces, decimal * (10 ** decimalPlaces));
return num * multiplier;
}
//Function end
var times = []
for (var i = 0; i < 50; i++) {
var startTime = new Date()
console.log(firstIntMultiple().toString())
times.push((new Date() - startTime) / 1000)
}
console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")
斯科特·萨耶特：
const num = 3.1415926535;
//Function start
const firstIntMultiple = (tol = 1e-10) => {
let c = 1;
while (Math.abs(num * c - Math.floor(num * c)) > tol) {
c += 1
}
return num * c
}
//Function end
var times = []
for (var i = 0; i < 50; i++) {
var startTime = new Date()
console.log(firstIntMultiple().toString())
times.push((new Date() - startTime) / 1000)
}
console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")
请注意，由于内部机制的细微差别，这些函数的结果会 return 略有不同。 Endothermic_Dragon 的答案试图找到 return 一个精确整数的倍数，而 Scott Sauyet 的答案试图找到使数字在整数的指定公差范围内的乘数。
可以通过在每个示例上添加更多的 pi 数字并减少对 Scott Sauyet 答案的容差来进一步扩展这些示例。
我最初打算在测试时使用 decimal.js (https://mikemcl.github.io/decimal.js/)，但是，结果证明 Scott 的方法非常慢 - 计算每次迭代需要 5.1243 秒，而在 Endothermic_Dragon 上，每次迭代花费 0.0002 秒。请注意，这是在 w3schools 上通过 10 次迭代完成的。
所有这些分析可以得出两个结论：
- Endothermic_Dragon 的答案在终止小数方面是可扩展的和准确的。
- Scott Sauyet 的回答耗费了一些时间，但给出了准确的答案。这在处理不终止的小数时特别有用，无论它们是无理数还是重复数。
此外，这里还有一个额外的测试，因为为什么不呢。
15 进制精度
Endothermic_Dragon:
const num = 3.141592653589793;
//Function start
const firstIntMultiple = () => {
var decimal = num % 1;
var decimalPlaces = num.toString().split(".")[1] ?.length || 0;
const gcd = (x, y) => (!y ? x : gcd(y, x % y));
var multiplier = 10 ** decimalPlaces / gcd(10 ** decimalPlaces, decimal * (10 ** decimalPlaces));
return num * multiplier;
}
//Function end
var times = []
for (var i = 0; i < 50; i++) {
var startTime = new Date()
console.log(firstIntMultiple().toString())
times.push((new Date() - startTime) / 1000)
}
console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")
斯科特·萨耶特：
const num = 3.141592653589793;
//Function start
const firstIntMultiple = (tol = 1e-15) => {
let c = 1;
while (Math.abs(num * c - Math.floor(num * c)) > tol) {
c += 1
}
return num * c
}
//Function end
var times = []
for (var i = 0; i < 50; i++) {
var startTime = new Date()
console.log(firstIntMultiple().toString())
times.push((new Date() - startTime) / 1000)
}
console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")
这是所有答案的总和。这样做的好处是它对每种输入都有一个 'fallback'。如果有终止小数，Endothermic_Dragon 的第一种方法就足够了。如果它是一个循环小数，那么一个明确找到答案的新方法就足够了。如果不够，则使用连分数作为后备。
请注意，我最后包含连分数的唯一原因是它有时会导致较小的小数点出现错误。我只想 'fix' 这个方法，但我不明白它是如何工作的，所以我用它作为后备方法。
//At the top so it is viewable
console.log(findMultiple(54.46333333333333)) //16339/300
console.log(findMultiple(8.333333333333333)) //25/3
console.log(findMultiple(14.05882352941176)) //Irrational
console.log(findMultiple(94.03820382038203)) //Irrational
console.log(findMultiple(623.0549383482724)) //1009349/1620
console.log(findMultiple(Math.PI)) //Irrational
console.log(findMultiple(13.000000221)) //1829587379722249/140737488355328
console.log(findMultiple(1.0000003333)) //1125900282105063/1125899906842624
//Main control
function findMultiple(num, interpretLiteral = false, epsilon = 1e-6) {
if (num.toString().length < 17 || num % 1 == 0 || interpretLiteral) {
return EndothermicDragonFirstMethod(num) //Terminating decimal
}
var checkRepeatingNum = CheckRepeating(num)
if (checkRepeatingNum != false) {
return Math.round(EndothermicDragonSecondMethod(num, checkRepeatingNum) * num) //Repeating decimal
} else {
return ScottSauyetFirstMethod(num, epsilon) //Continued fraction
}
}
//Predifined functions
//GCD
function gcd(x, y){return !y ? x : gcd(y, x % y)};
//Check if digits repeat, if they do, return repeat period
function CheckRepeating(num) {
var totalSearchLength = (num % 1).toString().split('.')[1].slice(0, -1).length
var numTemp1 = (num % 1).toString().split('.')[1].slice(0, -1).split('').reverse().join('')
for (var i = 1; i < Math.floor(totalSearchLength / 3); i++) {
var numTemp2 = numTemp1.slice(0, 3 * i)
var searchLength = i
bool = numTemp2.slice(0, searchLength) == numTemp2.slice(searchLength, 2 * searchLength) && numTemp2.slice(0, searchLength) == numTemp2.slice(2 * searchLength, 3 * searchLength)
if (bool) {
return searchLength
}
}
return false
}
//Terminating decimal
function EndothermicDragonFirstMethod(num) {
var decimal = num % 1;
var decimalPlaces = num.toString().split(".")[1]?.length || 0;
var multiplier = 10 ** decimalPlaces / gcd(10 ** decimalPlaces, decimal * (10 ** decimalPlaces));
return num * multiplier;
}
//Repeating decimal
function EndothermicDragonSecondMethod(num, repeatInterval) {
var numArray = num.toString().split('.')[1].slice(-repeatInterval).split('').reverse()
var restOfNum = num.toString().split('.')[1].slice(0, -repeatInterval * 3).split('').reverse()
var counter = 0;
var extraRepeat = 0;
restOfNum.every(el => {
if (el == numArray[counter]) {
extraRepeat++;
counter++;
if (counter == numArray.length) {
counter = 0
}
return true
}
return false
})
var repeatingPart = num.toString().split('.')[1].slice(-repeatInterval * 3 - extraRepeat, -repeatInterval * 2 - extraRepeat)
var notRepeatingPart = num.toString().split('.')[1].slice(0, -repeatInterval * 3 - extraRepeat)
var numerator = (parseInt(notRepeatingPart) * (parseInt("9".repeat(repeatingPart.length)))) + parseInt(repeatingPart)
var denominator = (parseInt("9".repeat(repeatingPart.length)) * (10 ** notRepeatingPart.length))
return denominator / gcd(numerator, denominator)
}
//Otherwise (irrational numbers or other)
function ScottSauyetFirstMethod(num, epsilon = 1e-6) {
const contFrac = (n, d = 1, count = Infinity) =>
count < 1 || d == 0 ? [] : [Math.floor(n / d)].concat(contFrac(d, n % d, count - 1))
const bestApprox = (n, d = 1, c) =>
contFrac(n, d, c)
.reduce((a, n, i) => [
...a,
{
n: a[i].n + n * a[i + 1].n,
d: a[i].d + n * a[i + 1].d
}
], [{
n: 0,
d: 1
}, {
n: 1,
d: 0
}])
.slice(2)
const firstIntMultiple = (x, epsilon) =>
bestApprox(x, 1)
.find(({
n,
d
}, i, a) => i == a.length - 1 || Math.abs(n / d - x) < epsilon)
.n
return firstIntMultiple(num, epsilon)
}
无论输入的内容是什么（即使是小数），这都会产生准确的答案！
我正在使用 Javascript 编写一个简单的 do...while 语句，目的是查看给定输入 num 的小数点长度，以及小数点的长度是否更大大于或等于 1，取 num 并将其添加到自身上，直到十进制长度等于 0。目前，它适用于长度为 1 的小数，但任何更大的，它都会停止。
预期的输出，例如当num为8.75时，应该是35，而不是17.5。
该系列应该需要 4 个步骤才能达到 35。
8.75
17.5
26.25
35
这是我的代码：
const num = 8.75;
var decimalLength = num.toString().split(".")[1].length;
let result = "";
let i = num;
do {
i = i + num;
result = result + num;
newLength = decimalLength;
} while (newLength < 0);
console.log(i);
您可以使用一些奇特的数学来获得不会一遍又一遍地循环的更明确的答案：
const num = 8.75;
var decimal = num % 1 //Decimal part
var decimalPlaces = num.toString().split(".")[1] ?.length || 0; //Get decimal places
//GCD function
const gcd = (x, y) => (!y ? x : gcd(y, x % y));
//GCD between decimal and 1, need to make it whole number to get multiplier, so multiply each with 10^[decimal places]
//Get what's remaining when divided by 10^[decimal places] as well, to see what to multiply by to get whole number
var multiplier = 10 ** decimalPlaces / gcd(10 ** decimalPlaces, decimal * 10 ** decimalPlaces)
//Use log change of base property to get value in power of 2
var outputExponent = Math.log(multiplier) / Math.log(2)
//Multiply number by multiplier
var outputValue = num * multiplier
console.log(outputExponent) //Power of 2 to multiply by to get whole number
console.log(outputValue) //The whole number itself
此版本使用递归函数和容差来处理浮点舍入错误。
const firstIntMultiple = (n, tol=1e-6, c = 1) =>
Math.abs(n * c - Math.floor(n * c)) < tol ? n * c : firstIntMultiple (n, tol, c + 1)
console .log (firstIntMultiple (8.75)) // 35/4
console .log (firstIntMultiple (8.333333333333334)) // 25/3
console .log (firstIntMultiple (14.058823529411764)) // 239/17
它通过乘以连续的整数而不是连续的加法来找到正确的版本，但它的想法是一样的。
我们可以很容易地用迭代方法替换递归版本，这对于没有很好的有理逼近的数字可能很有用。 （现在，传递 Math.PI 将 运行 进入递归限制。）
可能看起来像这样：
const firstIntMultiple = (n, tol=1e-6) => {
let c = 1;
while (Math.abs(n * c - Math.floor(n * c)) > tol) {
c += 1
}
return n * c
}
而对于 Math.PI，那将是 return 4272943.0000005495，整数 1e-6 范围内的第一个圆周率倍数。您可以根据需要调整公差。
更新 -- 一种完全不同的技术
另一种技术将利用 the fact that continued fractions 提供一种直接的方法来找到数字的最佳有理近似值。我们可以使用它来找到 pi 的十个最佳有理近似值，例如：
bestApprox (Math.PI, 1, 10) .map (({n, d}) => `${n}/${d}`)
// => ["3/1", "22/7", "333/106", "355/113", "103993/33102", "104348/33215",
// "208341/66317", "312689/99532", "833719/265381", "1146408/364913"]
然后，使用这些近似值，我们可以找到第一个与我们的目标值相距不远的值。
代码可能如下所示：
const contFrac = (n, d = 1, count = Infinity) =>
count < 1 || d == 0
? []
: [Math .floor (n / d)] .concat (contFrac (d, n % d, count - 1))
const bestApprox = (n, d = 1, c) =>
contFrac(n, d, c)
.reduce ((a, n, i) => [
...a,
{
n: a [i] .n + n * a [i + 1] .n,
d: a [i] .d + n * a [i + 1] .d
}
], [{n: 0, d: 1}, {n: 1, d: 0}])
.slice (2)
const firstIntMultiple = (x, ε = 1e-6) =>
bestApprox (x, 1)
.find (({n, d}, i, a) => i == a.length - 1 || Math.abs (n / d - x) < ε)
.n
console .log (firstIntMultiple (8.75)) // 35/4
console .log (firstIntMultiple (8.333333333333334)) // 25/3
console .log (firstIntMultiple (14.058823529411764)) // 239/17
console .log (firstIntMultiple (Math.PI)) // 353/113
console .log (firstIntMultiple (Math.PI, 1e-8)) // 103993/33102
我没有测试性能，但这应该相当不错，尤其是对于那些连分数早期包含大整数的数字。 （例如 pi 是 <3; 7, 15, 1, 292,...> 那 292 意味着 3 + (1 / (7 + (1 / (15 + 1 / 1)))) 或 355 / 113 是 pi 的极好近似值，事实上，它很好精确到小数点后六位。
我不知道这对 OP 有多大帮助，但它表明古老的数学 类 可能有一天会派上用场！。 ;-)
更新 2 - 现在有更多解释！
此版本通过检查测试值是否在原始值的 epsilon 范围内而不检查测试值的 ratio 来解决使用小值的第二种方法中的问题原始值的测试值在 1 的 epsilon 范围内。它也有一些小的清理和默认 epsilon 的较小值：
const contFrac = (n, d = 1, count = Infinity) =>
count < 1 || d == 0
? []
: [Math .floor (n / d)] .concat (contFrac (d, n % d, count - 1))
const bestApprox = (n, d = 1, count = Infinity) =>
contFrac(n, d, count)
.reduce ((a, n, i) => [
...a,
{
n: a [i] .n + n * a [i + 1] .n,
d: a [i] .d + n * a [i + 1] .d
}
], [{n: 0, d: 1}, {n: 1, d: 0}])
.slice (2)
const isClose = (x, y, ε) =>
y == 0 ? x < ε : (x / y > 1 - ε && x / y < 1 + ε)
const firstIntMultiple = (x, ε = 1e-8) =>
bestApprox (x, 1)
.find (({n, d}, i, a) => i == a.length - 1 || isClose (n / d, x, ε))
.n
console .log (firstIntMultiple (8.75)) // 35/4
console .log (firstIntMultiple (8.333333333333334)) // 25/3
console .log (firstIntMultiple (14.058823529411764)) // 239/17
console .log (firstIntMultiple (Math.PI)) // 103993/33102
console .log (firstIntMultiple (Math.PI, 1e-6)) // 353/113
console .log (firstIntMultiple (13.000000221)) // 58823532/4524887
console .log (firstIntMultiple (1.0000003333)) // 3000301/3000300
console .log (firstIntMultiple (1234/987654321)) // 6/4802209
.as-console-wrapper {min-height: 100% !important; top: 0}
说明
这里主要的功能还是firstIntMultiple，而且比较简单，就是搜索bestApprox的结果，找一个和我们目标数足够接近的有理逼近，然后returning 该结果的分子。 “足够接近”由 isClose 确定，它检查两个数字的比率是否在 1 - ε 和 1 + ε 之间，其中 ε 是一个可选参数，默认为 1e-8.
所以问题是 bestApprox 是如何工作的。为此，我们需要讨论 Continued Fractions。我不能在这里公正地对待他们，但希望我能描述得足够多，让他们对他们有所了解。
这是一个重复的无限简单连分数：
1
1 + ---------------------------------
1
2 + ----------------------------
1
2 + ---------------------
1
2 + ---------------
1
2 + ---------
2 + ...
这是一个连分数，因为我们在其他分数的分母中保留嵌套分数。它是无限的，因为……好吧，因为它会无限地继续——以一种显而易见的方式。这很简单，因为所有
分子是 1s.
不难用一点代数证明这代表 2.
这通常会缩写为这样的符号：
<1; 2, 2, 2, 2, ...>
其中所有值都是整数，第一个之后都是正值。
这些有一些优点。所有有理数都有一个有限的连分数表示，所有二次数都有一个重复的无限模式。但更重要的是，这些连分数的前缀包含对数字的最佳有理逼近。 （证明不是特别难，应该是非数学家也能看懂的，不过这里就不试了。）
我的意思是这些数字：
<1;> //=> 1
<1; 2> //=> 3/2
<1; 2, 2> //=> 7/5
<1; 2, 2, 2> //=> 17/12
<1; 2, 2, 2, 2> //=> 41/29
...
是 sqrt(2) 的连续更好的近似值，除了更高的分母，没有更好的近似值可用。也就是说，例如，在大于 12 和小于 29 的分母中，没有比 sqrt(2).
因此，通过计算一个数的部分连分数，我们可以找到所有最佳近似值，并最终找到一个能够得到我们正在寻找的倍数的近似值。
现在我们需要知道如何计算这些连分数，然后如何将它们的分式变成有理数。幸运的是，两者都很简单。
要找到连分数的元素，我们需要做的就是找到数字的下限，将其添加到我们的列表中，然后继续计算余数的倒数。
如果我们从 27/11 开始，那么第一个元素将是 floor(27/11) 或 2；余数是 5/11，它是 11/5 的倒数，下一位是它的底数，即 2，余数是 1/5，它的倒数是 5 没有余数。所以 27/11 可以写成 <2; 2, 5>.
如果我们从 pi 开始，那么我们的第一个元素将是 3，然后我们将继续 0.14159265358979312 的倒数，即 7.062513305931052，下一个元素将是 7。取余数的倒数，得到15.996594406684103，下一个元素为15。该余数的倒数是 1.0034172310150002，因此下一个元素是 1。然后余数的倒数变得更大，达到 292.63459087501246。我们可以继续得到这样的结果：
<3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 3, 3, 2, 1, ...>
没有明显的规律。但是 292 的高值告诉我们 <3; 7, 15, 1> 或 355/113 是 pi.
函数 contFrac 按照描述执行此算法。
现在，要将偏数转换为有理数，我们可以使用简单的递归。在<a_0; a_1, a_2, a_3, ...>中，第一个近似值是a_0，我们写成a_0/1。第二个是 a_0 + (1 / a_1) 或 (a_0 * a_1) / a_1。之后，我们可以通过以下简单公式找到第 (k + 2) 个值：n_(k + 2) = a_(k + 2) * n_(k + 1) + n_k 和 d_(k + 2) = a_(k + 2) * d_(k + 1) + d_k.
所以对于 <3; 7, 15, 1>，我们从 3/1 开始，然后是 22/7，然后我们的下一个值是 (15 * 22 + 3) / (15 * 7 + 1) 或 333/106，然后是 (1 * 333 + 22) / (1 * 106 + 7) 或 355/113。该代码使用了一个小技巧，将分子和分母向后扩展了两步，这样我们就可以对每一步都使用递归，然后简单地将这两个值从最终结果中切出。
我们已经有了。通过对一个数使用最好的有理近似值，我们可以快速找到最小的整数，在很小的公差范围内，它是该数的倍数。
两个相互矛盾的答案。哪个更好？在你测试之前没有办法知道。所以，这就是这个新答案试图做的。
这些 'tests'（如果你愿意）运行 每个函数 50 次，在清除控制台和记录时间平均值之前对每次迭代进行计时。
8 位小数精度
Endothermic_Dragon:
const num = 3.14159265;
//Function start
const firstIntMultiple = () => {
var decimal = num % 1;
var decimalPlaces = num.toString().split(".")[1] ?.length || 0;
const gcd = (x, y) => (!y ? x : gcd(y, x % y));
var multiplier = 10 ** decimalPlaces / gcd(10 ** decimalPlaces, decimal * (10 ** decimalPlaces));
return num * multiplier;
}
//Function end
var times = []
for (var i = 0; i < 50; i++) {
var startTime = new Date()
console.log(firstIntMultiple().toString())
times.push((new Date() - startTime) / 1000)
}
console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")
斯科特·萨耶特：
const num = 3.14159265;
//Function start
const firstIntMultiple = (tol = 1e-8) => {
let c = 1;
while (Math.abs(num * c - Math.floor(num * c)) > tol) {
c += 1
}
return num * c
}
//Function end
var times = []
for (var i = 0; i < 50; i++) {
var startTime = new Date()
console.log(firstIntMultiple().toString())
times.push((new Date() - startTime) / 1000)
}
console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")
10 进制精度
Endothermic_Dragon:
const num = 3.1415926535;
//Function start
const firstIntMultiple = () => {
var decimal = num % 1;
var decimalPlaces = num.toString().split(".")[1] ?.length || 0;
const gcd = (x, y) => (!y ? x : gcd(y, x % y));
var multiplier = 10 ** decimalPlaces / gcd(10 ** decimalPlaces, decimal * (10 ** decimalPlaces));
return num * multiplier;
}
//Function end
var times = []
for (var i = 0; i < 50; i++) {
var startTime = new Date()
console.log(firstIntMultiple().toString())
times.push((new Date() - startTime) / 1000)
}
console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")
斯科特·萨耶特：
const num = 3.1415926535;
//Function start
const firstIntMultiple = (tol = 1e-10) => {
let c = 1;
while (Math.abs(num * c - Math.floor(num * c)) > tol) {
c += 1
}
return num * c
}
//Function end
var times = []
for (var i = 0; i < 50; i++) {
var startTime = new Date()
console.log(firstIntMultiple().toString())
times.push((new Date() - startTime) / 1000)
}
console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")
请注意，由于内部机制的细微差别，这些函数的结果会 return 略有不同。 Endothermic_Dragon 的答案试图找到 return 一个精确整数的倍数，而 Scott Sauyet 的答案试图找到使数字在整数的指定公差范围内的乘数。
可以通过在每个示例上添加更多的 pi 数字并减少对 Scott Sauyet 答案的容差来进一步扩展这些示例。
我最初打算在测试时使用 decimal.js (https://mikemcl.github.io/decimal.js/)，但是，结果证明 Scott 的方法非常慢 - 计算每次迭代需要 5.1243 秒，而在 Endothermic_Dragon 上，每次迭代花费 0.0002 秒。请注意，这是在 w3schools 上通过 10 次迭代完成的。
所有这些分析可以得出两个结论：
- Endothermic_Dragon 的答案在终止小数方面是可扩展的和准确的。
- Scott Sauyet 的回答耗费了一些时间，但给出了准确的答案。这在处理不终止的小数时特别有用，无论它们是无理数还是重复数。
此外，这里还有一个额外的测试，因为为什么不呢。
15 进制精度
Endothermic_Dragon:
const num = 3.141592653589793;
//Function start
const firstIntMultiple = () => {
var decimal = num % 1;
var decimalPlaces = num.toString().split(".")[1] ?.length || 0;
const gcd = (x, y) => (!y ? x : gcd(y, x % y));
var multiplier = 10 ** decimalPlaces / gcd(10 ** decimalPlaces, decimal * (10 ** decimalPlaces));
return num * multiplier;
}
//Function end
var times = []
for (var i = 0; i < 50; i++) {
var startTime = new Date()
console.log(firstIntMultiple().toString())
times.push((new Date() - startTime) / 1000)
}
console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")
斯科特·萨耶特：
const num = 3.141592653589793;
//Function start
const firstIntMultiple = (tol = 1e-15) => {
let c = 1;
while (Math.abs(num * c - Math.floor(num * c)) > tol) {
c += 1
}
return num * c
}
//Function end
var times = []
for (var i = 0; i < 50; i++) {
var startTime = new Date()
console.log(firstIntMultiple().toString())
times.push((new Date() - startTime) / 1000)
}
console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")
这是所有答案的总和。这样做的好处是它对每种输入都有一个 'fallback'。如果有终止小数，Endothermic_Dragon 的第一种方法就足够了。如果它是一个循环小数，那么一个明确找到答案的新方法就足够了。如果不够，则使用连分数作为后备。
请注意，我最后包含连分数的唯一原因是它有时会导致较小的小数点出现错误。我只想 'fix' 这个方法，但我不明白它是如何工作的，所以我用它作为后备方法。
//At the top so it is viewable
console.log(findMultiple(54.46333333333333)) //16339/300
console.log(findMultiple(8.333333333333333)) //25/3
console.log(findMultiple(14.05882352941176)) //Irrational
console.log(findMultiple(94.03820382038203)) //Irrational
console.log(findMultiple(623.0549383482724)) //1009349/1620
console.log(findMultiple(Math.PI)) //Irrational
console.log(findMultiple(13.000000221)) //1829587379722249/140737488355328
console.log(findMultiple(1.0000003333)) //1125900282105063/1125899906842624
//Main control
function findMultiple(num, interpretLiteral = false, epsilon = 1e-6) {
if (num.toString().length < 17 || num % 1 == 0 || interpretLiteral) {
return EndothermicDragonFirstMethod(num) //Terminating decimal
}
var checkRepeatingNum = CheckRepeating(num)
if (checkRepeatingNum != false) {
return Math.round(EndothermicDragonSecondMethod(num, checkRepeatingNum) * num) //Repeating decimal
} else {
return ScottSauyetFirstMethod(num, epsilon) //Continued fraction
}
}
//Predifined functions
//GCD
function gcd(x, y){return !y ? x : gcd(y, x % y)};
//Check if digits repeat, if they do, return repeat period
function CheckRepeating(num) {
var totalSearchLength = (num % 1).toString().split('.')[1].slice(0, -1).length
var numTemp1 = (num % 1).toString().split('.')[1].slice(0, -1).split('').reverse().join('')
for (var i = 1; i < Math.floor(totalSearchLength / 3); i++) {
var numTemp2 = numTemp1.slice(0, 3 * i)
var searchLength = i
bool = numTemp2.slice(0, searchLength) == numTemp2.slice(searchLength, 2 * searchLength) && numTemp2.slice(0, searchLength) == numTemp2.slice(2 * searchLength, 3 * searchLength)
if (bool) {
return searchLength
}
}
return false
}
//Terminating decimal
function EndothermicDragonFirstMethod(num) {
var decimal = num % 1;
var decimalPlaces = num.toString().split(".")[1]?.length || 0;
var multiplier = 10 ** decimalPlaces / gcd(10 ** decimalPlaces, decimal * (10 ** decimalPlaces));
return num * multiplier;
}
//Repeating decimal
function EndothermicDragonSecondMethod(num, repeatInterval) {
var numArray = num.toString().split('.')[1].slice(-repeatInterval).split('').reverse()
var restOfNum = num.toString().split('.')[1].slice(0, -repeatInterval * 3).split('').reverse()
var counter = 0;
var extraRepeat = 0;
restOfNum.every(el => {
if (el == numArray[counter]) {
extraRepeat++;
counter++;
if (counter == numArray.length) {
counter = 0
}
return true
}
return false
})
var repeatingPart = num.toString().split('.')[1].slice(-repeatInterval * 3 - extraRepeat, -repeatInterval * 2 - extraRepeat)
var notRepeatingPart = num.toString().split('.')[1].slice(0, -repeatInterval * 3 - extraRepeat)
var numerator = (parseInt(notRepeatingPart) * (parseInt("9".repeat(repeatingPart.length)))) + parseInt(repeatingPart)
var denominator = (parseInt("9".repeat(repeatingPart.length)) * (10 ** notRepeatingPart.length))
return denominator / gcd(numerator, denominator)
}
//Otherwise (irrational numbers or other)
function ScottSauyetFirstMethod(num, epsilon = 1e-6) {
const contFrac = (n, d = 1, count = Infinity) =>
count < 1 || d == 0 ? [] : [Math.floor(n / d)].concat(contFrac(d, n % d, count - 1))
const bestApprox = (n, d = 1, c) =>
contFrac(n, d, c)
.reduce((a, n, i) => [
...a,
{
n: a[i].n + n * a[i + 1].n,
d: a[i].d + n * a[i + 1].d
}
], [{
n: 0,
d: 1
}, {
n: 1,
d: 0
}])
.slice(2)
const firstIntMultiple = (x, epsilon) =>
bestApprox(x, 1)
.find(({
n,
d
}, i, a) => i == a.length - 1 || Math.abs(n / d - x) < epsilon)
.n
return firstIntMultiple(num, epsilon)
}
无论输入的内容是什么（即使是小数），这都会产生准确的答案！