我们是否可以假设对于所有正整数x，都有x == (int)sqrt(x * x)？

Question

我们是否可以假设对于所有正整数x，都有x == (int)sqrt(x * x)？

4

在 C++ 中，sqrt 函数只能用于 double 类型的值。

如果我们使用整数（无符号长整型），我们能确定：

x == sqrt(x * x)

对于任何满足 x * x <= MAXIMUM_VALUE 的正数 x，是否有影响取决于机器结构和编译器？

- Jegors Čemisovs

2

有趣的问题，但是"sqrt函数仅处理双精度值"吗？ C（因此也包括C++）提供了用于计算float、double和long double平方根的函数。 - Andrew Henle

5

选择一门语言。答案将因语言不同而异。 - dbush

2

我没有看到C标准甚至IEEE 754对sqrt有任何实现约束或特殊要求。 - Eugene Sh.

1

这个回答解决了你的问题吗？IEEE double such that sqrt(x*x) ≠ x - phuclv

1

可能是重复问题：C++ sqrt函数对完全平方数的精度 - rustyx

显示剩余9条评论

5个回答

0

试一下吧。是的，在Java中可以工作，对于非负数。甚至对于long类型也适用，与常见观点相反。

class Code {
    public static void main(String[] args) throws Throwable {
        for (long x=(long)Math.sqrt(Long.MAX_VALUE);; --x) {
            if (!(x == (long)Math.sqrt(x * x))) {
                System.err.println("Not true for: "+x);
                break;
            }
        }
        System.err.println("Done");
    }
}

（第一个不能工作的数字是3037000500L，当平方时将变为负数。）

即使对于长整型而言，可测试值的范围也约为2 ^ 31或2 * 10 ^ 9，因此对于这种微不足道的事情来说，检查每个单独的值是合理的。您甚至可以针对32位值强制执行合理的加密功能 - 这是更多人应该意识到的内容。对于完整的64位则无法有效运行。

- Tom Hawtin - tackline

0

我认为我们可以相信。

将浮点数强制转换为整数是只取其整数部分。例如，我相信你可能会关心sqrt(4)产生的浮点数，如1.999...9，它被强制转换为1。（产生2.000...1也没问题，因为它将被强制转换为2。）

但是浮点数4就像

(1 * 2^-0 + 0 + 2^-1 + ... + 0 * 2^-23) * 2²

根据Floating-point arithmetic。

这意味着它不能小于4，如3.999...9。因此，该数字的sqrt也不能小于

(1 * 2^-0) * 2

因此，对于一个整数的平方的sqrt至少会产生一个浮点数，该浮点数大于但足够接近该整数。

- ghchoi

4是一个容易处理的情况，可以精确地表示为浮点数。但是考虑2^32-1的平方，即(2^64-2^33+1)，很明显在23位或52位中无法精确表示。 - MSalters

0

BigInteger - `sqrt(since 9)`

需要更严格的溢出可能性约束的用例可以使用 BigInteger。
BigInteger 可以适用于任何实际用例。
但对于普通用例来说，这可能不是高效的。

约束条件

BigInteger Limits

BigInteger 必须支持范围在 -2^Integer.MAX_VALUE（不包括）到 +2^Integer.MAX_VALUE（不包括）之间的值，并且可能支持该范围之外的值。当 BigInteger 构造函数或方法生成超出支持范围的值时，会抛出 ArithmeticException 异常。可能质数值的范围是有限制的，可能小于 BigInteger 的完全支持正数范围。该范围必须至少为 1 到 2500000000。

实现注意事项：
在参考实现中，当 BigInteger 构造函数或操作的结果超出支持范围 -2^Integer.MAX_VALUE（不包括）到 +2^Integer.MAX_VALUE（不包括）时，会抛出 ArithmeticException 异常。

以字节形式初始化数组时的大小限制数组

以字符串初始化时的长度限制

绝对不支持`1/0`

jshell> new BigInteger("1").divide(new BigInteger("0"))
|  Exception java.lang.ArithmeticException: BigInteger divide by zero
|        at MutableBigInteger.divideKnuth (MutableBigInteger.java:1178)
|        at BigInteger.divideKnuth (BigInteger.java:2300)
|        at BigInteger.divide (BigInteger.java:2281)
|        at (#1:1)

一个示例代码

import java.math.BigInteger;
import java.util.Arrays;
import java.util.List;

public class SquareAndSqrt {

    static void valid() {
        List<String> values = Arrays.asList("1", "9223372036854775807",
            "92233720368547758079223372036854775807", 
            new BigInteger("2").pow(Short.MAX_VALUE - 1).toString());

        for (String input : values) {
            final BigInteger value = new BigInteger(input);
            final BigInteger square = value.multiply(value);
            final BigInteger sqrt = square.sqrt();

            System.out.println("value: " + input + System.lineSeparator()
                + ", square: " + square + System.lineSeparator()
                + ", sqrt: " + sqrt + System.lineSeparator()
                + ", " + value.equals(sqrt));

            System.out.println(System.lineSeparator().repeat(2)); // pre java 11 - System.out.println(new String(new char[2]).replace("\0", System.lineSeparator()));
        }
    }

    static void mayBeInValid() {
        try {
            new BigInteger("2").pow(Integer.MAX_VALUE);
        } catch (ArithmeticException e) {
            System.out.print("value: 2^Integer.MAX_VALUE, Exception: " + e);
            System.out.println(System.lineSeparator().repeat(2));
        }
    }

    public static void main(String[] args) {
        valid();
        mayBeInValid();
    }
}

- Thiyanesh

-1

在cmath库中，sqrt函数总是将参数转换为double或float，因此double或float的范围比unsigned long long更大，因此它总是返回正数。您可以参考以下链接： https://learn.microsoft.com/en-us/cpp/standard-library/cmath?view=msvc-170, https://learn.microsoft.com/en-us/cpp/c-language/type-float?view=msvc-170

- ayush maheshwari

2

这是不正确的。范围更大，但精度较低（52位与64位）。请注意：大小取自链接的VC++；其他实现可能具有略微不同的精度。 - MSalters

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rzwitserloot · Accepted Answer

在Java中，Math.sqrt(x)的参数是一个双精度浮点型的值。你提到了对于参数x，x * x的结果小于Integer.MAX_VALUE。在Java中，所有的整数都可以用double类型来完美表示。Java中的double类型被明确定义为IEEE-754标准下的64位双精度浮点型数据，其中52位用于尾数；因此，在Java中，double类型能够完美地表示从-2^52到+2^52之间的所有整数值，这包括所有int类型的值（因为其定义为有符号的32位数），但并不包括所有long类型的值（因为其定义为有符号的64位数；64位大于52位，所以不能覆盖所有值）。

因此，当x * x从int类型转换为double类型时，不会失去精度。随后，对这个数值调用Math.sqrt()方法将得到能够被double类型完美表示的结果（即因为它就是x，根据x * x能够被int类型表示，所以x也一定可以被表示为int），因此，是的，这种方法对于所有x值都适用。

但，嘿，为什么不试试呢？

public static void main(String[] args) {
    int i = 1;
    while (true) {
        if (i * i < 0) break;
        int j = (int) Math.sqrt(i * i);
        if (i != j) System.out.println("Oh dear! " + i + " -> " + j);

        i++;
    }
    System.out.println("Done at " + i);
}

> Done at 46341

因此通过全面尝试证明它。结果是不存在这样的任何long值，使得x * x仍然适合(因此是<2^63-1)并且具有x == (long) Math.sqrt(x * x);的属性。这可能是因为在x * x处，该数字完美地适合一个长整型，即使不是所有这么大的整数都是如此。证明：

long p = 2000000000L;
for (; true; p++) {
    long pp = p * p;
    if (pp < 0) break;
    long q = (long) Math.sqrt(pp);
    if (q != p) System.out.println("PROBLEM: " + p + " -> " + q);
}
System.out.println("Abort: " + p);

> Abort: 3037000500

如果存在任何一个数字不符合条件，那么在这个高端范围内至少会有一个。从0开始需要很长时间。

但是我们知道sqrt是否总会为完全平方数返回精确值，还是可能会略微不准确？

我们应该知道-它是Java。与C不同，几乎所有东西都是“明确定义的”，如果JVM未能按照规定产生精确答案，它就不能合法地称呼自己为JVM。 Math.sqrt文档提供的余地不足以使除了精确的x之外的任何答案成为合法实现，因此，是的，这是一个保证。

理论上，JVM对浮点数有一些非常小的余地，strictfp禁用了这种余地，但是[A]这更多关于使用80位寄存器来表示数字而不是64位，这不可能破坏这个假设，[B] 一段时间以前，一个java标签问题出现了，显示strictfp对任何硬件和任何VM版本都没有影响，唯一可行的结果是15年前的一个不可重现的事情。我非常有信心地说，无论硬件或VM版本如何，这将始终成立。

我们是否可以假设对于所有正整数x，都有x == (int)sqrt(x * x)？

BigInteger - sqrt(since 9)

约束条件

绝对不支持1/0

一个示例代码

BigInteger - `sqrt(since 9)`

绝对不支持`1/0`