检验方程无理数

这取决于上下文，但您可能想说，非常接近简单有理数的浮点数应标识为有理数，否则应将它们标识为可能的无理数。你必须选择"非常接近"和"简单有理数"的定义。

对于相对较小的数字(例如绝对值低于 100(，您可能会说简单有理数是分母较小的有理数，例如 2/3，例如分母小于 100 的有理数。您对"非常接近"的定义可能是差异的绝对大小很小，例如低于 10^-6，或者您可能要求数字接近分母平方的 1000 倍。对于大多数目的，这就足够了。

具有小分母的数的有理逼近理论是称为丢番图逼近的数论的一部分。您可能使用的一种工具是数字的简单连续分数扩展，例如 pi = 3+1/(7+1/(15+1/(1+1/292+...)))和e-1=1+1/(1+1/(2+1/(1+1/(1+1/(4+1/(1+1/(1+1/(6+...))). 您可以递归计算这些，尽管您很快就会耗尽精度。当你截断这样的表达式时，你会得到一个很好的有理近似，比如pi~3，或pi~22/7，pi~355/113，或e~193/71。这些给出候选有理数，其分母很小，非常接近。简单连续分数中的大系数意味着该数字具有良好的有理近似。

数不会以这种方式被检测为有理数，例如，如果对分母使用阈值 100，则为 1/500。但是，您将能够识别 1/3.0f 为理性，而 Math.sqrt(2.0(*Math.sqrt(8.0(，您将拒绝 Math.sqrt(2.0(。

我不知道是否有标准方法来确定像 6.73241 x 10^31 这样的大型浮点数的复杂性。这甚至可以是一个整数，但你没有精度来判断。您可能会说接近平滑整数的数字很简单。平滑意味着素数分解中没有大的素数。虽然分解大数通常很难，但分解平滑数字并不是那么糟糕，因为您只需要测试几个可能的素因数。当您甚至无法测试附近数字的平滑度时，您可以将数字的对数与小素数的对数组合进行比较。这可能意味着大素数不会被识别为有理数，但如果您关心，创纪录的素数通常与平滑数相差 1，例如 2**57885161-1。

在非常大的浮点数和小数之间，您可以使用某种复杂性度量，该度量结合了可能分子的简单性和可能分母的简单性。因此，对于 10^6 和 10^9 之间的数字，您可能会决定只容忍最多 10 的分母，并且您可能要求与其中一个数字的差值小于 10^-4。

确定sqrt(rational)是否不合理是相当简单的。方法如下：

将rational参数写为带有m和n整数和互质数的m/n，即gcd(n, m) = 1。现在假设存在m/n的有理平方根r。如果r = s/t s和t整数和互质，我们将有：

s^2/t^2 = rˆ2 = m/n

或

n * s * s = m * t * t

特别是s * s会除m * t * t，由于s和t没有共同的素数，s * s实际上会除m。换句话说，我们将有 (1( s * s <= m 和 (2( m % (s * s) = 0(mod 操作(。因此，可以使用以下例程非常轻松地计算s的所有候选项

1. [初始化] 设S为除数和d := 1的空集合。
2. [选中] 如果 m % (d * d) = 0，则将d添加到S
3. [增量] 设置d := d + 1
4. [重复] 如果d * d <= m转到 2
5. [完] 返回S

以同样的方式，我们可以得出结论，t满足(1(t * t <= n和(2(n % (t * t) = 0。我们可以使用与上面相同的例程来计算n的所有平方除数的集合T(只需将S替换为T，m替换为n(。

最后，我们必须枚举(s, t) S x T的所有对

m * s * s = n * t * t

使用精确的整数算术，这是完全可能的。如果没有找到对(s, t)，那么sqrt(m/n)将是非理性的。

例

让我们假设我们不知道sqrt(100/81)是理性10/9，让我们使用上面给出的算法来推断它：

首先，我们计算 100 的平方除数的集合D。以下是算法的痕迹：

`d = 1` Yes, `100 % (1 * 1) = 0`
`d = 2` Yes, `100 % (2 * 2) = 0`
`d = 3` No, `100 % (3 * 3) = 1`
`d = 4` No, `100 % (4 * 4) = 4`
`d = 5` Yes, `100 % (5 * 5) = 0`
`d = 6` No, `100 % (6 * 6) = 28`
`d = 7` No, `100 % (7 * 7) = 2`
`d = 8` No, `100 % (8 * 8) = 36`
`d = 9` No, `100 % (9 * 9) = 19`
`d = 10` Yes, `100 % (10 * 10) = 0`
End: `11 * 11 > 100`.

所以，D = {1, 2, 5, 10}.现在让我们计算T，81的平方除数

`d = 1`, Yes
`d = 2`, No (remainder = 1)
`d = 3`, Yes
`d = 4`, No (remainder = 1)
`d = 5`, No (remainder = 6)
`d = 6`, No (remainder = 9)
`d = 7`, No (remainder = 32)
`d = 8`, No (remainder = 17)
`d = 9`, Yes
End: `10 * 10 > 81`.

所以，T = {1, 3, 9}

现在我们枚举D x T (s, t)的所有对，并将81 * s * s与100 * t * t进行比较。这些对是：

(1, 1), (2, 1), (5, 1), (10, 1)
(1, 3), (2, 3), (5, 3), (10, 3)
(1, 9), (2, 9), (5, 9), (10, 9)

我们看到最后一个(10,9(满足81 * 10 * 10 = 100 * 9 * 9 .因此sqrt(100/81) = 10/9.如果选择这个例子，使得没有一对满足方程，那么平方根将是无理的。

这是一种可能性。 第一步是找到下一个最小和最大的浮点数(这是导致 prevFloat 和 nextFloat 的各种分配(。 之后，我们逐步浏览所有可能的有理数，分母低于某个阈值，寻找浮点数之间适合的东西。 如果在用完潜在分母之前找不到分数，则会报告 NaN . 该函数最终在 O(maxDenom) 中运行。

function asRational(number) {
    var maxDenom = 1000,
        sign = number < 0 ? "-" : "+",
        absVal = Math.abs(number),
        integer = Math.floor(absVal),
        fractionalPart = absVal-integer,
        asBinary = fractionalPart.toString(2),
        prevAsBinary = asBinary.replace(/10*$/,function(match) {
            return "0"+Array(match.length).join("1");
        }),
        nextAsBinary = asBinary.replace(/01*$/,function(match) {
            return "1"+Array(match.length).join("0");
        }),
        prevFloat = parseFloat(prevAsBinary,2),
        nextFloat = parseFloat(nextAsBinary,2),
        numerator = 0;
    for ( var denominator = 1 ; denominator <= maxDenom ; denominator++ ) {
        while ( numerator < denominator*prevFloat ) {
            numerator++;
        }
        if ( numerator <= denominator*nextFloat ) {
            return {
                "sign":sign,
                "integer":integer,
                "numerator":numerator,
                "denominator":denominator
            };
        }
    }
    return NaN;
}
function rationalToString(rational) {
    if ( !! rational ) {
        return rational.sign+"("+rational.integer
            +"+"+rational.numerator+"/"+rational.denominator+")";
    } else {
        return "NaN";
    }
}
function parseFloat(asString,radix) {
    var power = asString.length-asString.indexOf(".")-1,
        asFloat = parseInt(asString.replace(".",""),radix);
    for ( var i = 0 ; i < power ; i++ ) {
        asFloat /= radix;
    }
    return asFloat;
}
var paras = document.getElementsByTagName("p");
for ( var i = 0 ; i < paras.length ; i++ ) {
    paras[i].textContent
        = paras[i].id+"="+rationalToString(asRational(eval(paras[i].id)));
}

<html>
 <head>
 </head>
 <body>
  <p id="5/3"></p>
  <p id="100/999"></p>
  <p id="99/1000"></p>
  <p id="100/1001"></p>
  <p id="1000/10000"></p>
 </body>
</html>