na Ramanujan 数是什么——为什么我在接近 2^63 的值中出现错误？

Question

给定一个数字，测试它是否是 Ramanujan 数（在我们的课程中定义为两种不同方式的两个立方体的总和）。它必须在 n^(1/3) 时间内运行。我的代码正在运行——有时。随着测试值接近 2^63 -1，我收到了一些随机错误。奇怪的是，在我更改计数器的起始值以修复不同的错误之前，我通过了该范围内数字的测试。谁能告诉我为什么会这样？我设置了一个 for 循环来为 a^3 创建值。然后我设置 b=(na^3)^(1/3) 的值。然后我测试 b 看它是否是一个整数。如果是这样，请打破循环。在此处插入一个 if 测试以使代码正常工作，但我不知道为什么需要这样做，这就是这个问题的要点。此 if 语句为高于和低于 n=2^63 的值设置了两个不同的 for 循环n < 2^63 的第二个循环从 c=a+1 开始，所以我不重复。这和第一个一样。n > 2^63 的第二个循环从 c=a 开始。为什么这会有所作为？为什么相同的代码不适用于更小和更大的数字？对不起，我的代码太幼稚了，我才刚刚起步，很多功能在我的课程中都是禁止使用的。（例如，我不能使用 floor() 并且也不允许为它编写自己的函数）。public class Ramanujan {public static boolean isRamanujan(long n) {    if (n <= 0) return false;    long a3 = 0;    long c3 = 0;    double b = 0;    double d = 0;    for (int a = 1; a < n; a++) {        a3 = (long) a * a * a;        if (a3 > n) break;        b = Math.cbrt(n - a3);        if (b == (int) b) break;    }    if (n > Math.pow(2, 62)) {        for (int c = (int) Math.cbrt(a3); c < n; c++) {            c3 = (long) c * c * c;            if (c3 > n) break;            d = Math.cbrt(n - c3);            if (d == (int) d) break;        }    }    else {        for (int c = (int) Math.cbrt(a3) + 1; c < n; c++) {            c3 = (long) c * c * c;            if (c3 > n) break;            d = Math.cbrt(n - c3);            if (d == (int) d) break;        }    }    if (a3 + (long) b * b * b == c3 + (long) d * d * d && b * b * b != c3) return true;    return false;}public static void main(String[] args) {    long n = Long.parseLong(args[0]);    StdOut.println(isRamanujan(n));}}关于为什么我需要区分较大和较小数字的任何见解？

Answer 1

n当超过 a 可以容纳的值时，您会得到奇怪的结果long，即Math.pow(2, 63) == Long.MAX_VALUE。到那时，n就会出现数值溢出。

final long l = Long.MAX_VALUE; // == 2^63

System.out.println(l); // 9223372036854775807

System.out.println(l + 1); // -9223372036854775808

Answer 2

当甚至超过 type 的范围时，由于算术溢出，您会得到大值的随机错误。您应该为所有整数变量使用 type以减少这种可能性，并确保中间结果不超过 type 的范围。intMath.cbrt(a3)Math.cbrt(n - a3)intlonglong

这是一个使用单个循环的更简单的实现，计算方式的数量：

public class Ramanujan {

    public static boolean isRamanujan(long n) {

        if (n <= 0) return false;

        int count = 0;

        for (long a = 1;; a++) {

            long a3 = a * a * a;

            if (a3 > n - a3) break;

            long b = (long)Math.cbrt(n - a3);

            if (a3 + b * b * b == n) count++;

        }

        return count >= 2;

    }

    public static void main(String[] args) {

        if (args.length == 1) {

            long n = Long.parseLong(args[0]);

            StdOut.println(isRamanujan(n));

        } else

        if (args.length == 2) {

            long n1 = Long.parseLong(args[0]);

            long n2 = Long.parseLong(args[1]);

            for (long n = n1; n <= n2; n++) {

                if (isRamanujan(n))

                    StdOut.println(n);

                if (n == Long.MAX_VALUE) // handle n2 == Long.MAX_VALUE

                    break;

            }

        } else {

            StdOut.println("usage: Ramanujan n1 [n2]");

        }

    }

}

Answer 3

问题在于乘以a and c类型变量int来计算立方体。需要将cast每个变量long乘以。

例子， a3 = (long) a * (long) a * (long) a;

Answer 4

long 可以容纳的最大数字（在 Java 中）是 (2 ^ 63) - 1 (Long.MAX_VALUE)。你为什么要计算 Math.cbrt(a3) ？如果 a3 = a * a * a，那么您已经知道 Math.cbrt(a3) 是什么。

如果 n > 9223372036854774272 Math.cbrt of 9223372036854774273 是 2097152 并且如果你立方体你因为溢出而得到负数，那么你的代码有问题。