快速检查长整数是否为立方体的方法（Java）

Question

我正在编写一个程序，我需要在其中检查某些大数（立方体的排列）是否为立方体（对于某些 n 等于 n^3）。

目前我只是使用方法

static boolean isCube(long input) {
    double cubeRoot = Math.pow(input,1.0/3.0);
    return Math.round(cubeRoot) == cubeRoot;
}

但是在处理大量数字（10 位以上）时这会非常慢。有没有更快的方法来确定整数是否是立方体？

Answer 1

只有 2^21 个不会溢出很长的立方体（如果允许负数，则为 2^22 - 1），因此您可以只使用 HashSet 查找。

Answer 2

请定义非常秀。这是一个测试程序：

public static void main(String[] args) {
    for (long v = 1; v > 0; v = v * 10) {
        long start = System.nanoTime();
        for (int i = 0; i < 100; i++)
            isCube(v);
        long end = System.nanoTime();
        System.out.println(v + ": " + (end - start) + "ns");
    }
}
static boolean isCube(long input) {
    double cubeRoot = Math.pow(input,1.0/3.0);
    return Math.round(cubeRoot) == cubeRoot;
}

输出为：

1: 290528ns
10: 46188ns
100: 45332ns
1000: 46188ns
10000: 46188ns
100000: 46473ns
1000000: 46188ns
10000000: 45048ns
100000000: 45048ns
1000000000: 44763ns
10000000000: 45048ns
100000000000: 44477ns
1000000000000: 45047ns
10000000000000: 46473ns
100000000000000: 47044ns
1000000000000000: 46188ns
10000000000000000: 65291ns
100000000000000000: 45047ns
1000000000000000000: 44477ns

我没有看到 "large" 数字对性能的影响。

Answer 3

您可以先通过对给定数字进行取模测试来淘汰大量候选人。例如，以数字 819 为模的立方体只能采用以下 45 值。

 0  125  181  818  720  811  532  755  476
 1  216   90  307  377  694  350  567  442
 8  343  559  629  658  351  190   91  469
27  512  287  252  638  118  603  161  441
64  729   99  701  792  378  260  468  728

因此，在几乎 95% 的均匀分布情况下，您实际上不必计算立方根。

Answer 4

Hacker's Delight 书中有一个简短而快速的整数立方根函数，值得移植到 64 位长整数，见下文。

看来测试一个数是否为完美立方比实际计算立方根要快。 Burningmath has a technique that uses the "digital root”（对数字求和。重复直到它是一个数字）。如果数字根是 0、1 或 8，则您的数字可能是一个完美的立方体。

此方法对于您排列（数字？）数字的情况可能非常有价值。如果您可以通过数字根排除一个数，则所有排列也将被排除。

他们还描述了一种基于检查完美立方体的主要因素的技术。这看起来最适合心算，因为我认为因式分解比计算机上的立方根运算要慢。

无论如何，数字根可以快速输入计算机，您甚至可以将数字作为一串数字开始。您仍然需要一个除以 10 的循环，但您的起点是输入的数字总和，而不是整数，因此不会有很多除法。（整数除法比当前 CPU 上的乘法慢一个数量级，但除以编译时间常数可以是 optimized to multiply+shift with a fixed-point inverse。希望 Java JIT 编译器也使用它，甚至可能使用它用于运行时常量。)

这加上（input % 819 -> 搜索 table 的 45 个条目）将排除 lot 输入作为不可能完美的立方体。 IDK 如果二进制搜索、线性搜索或 hash/set 最好。

这些测试可能是 of just storing the set of longs that are perfect cubes in a data structure that allows quick is-present checks. (e.g. HashSet) 的前端。是的，缓存未命中的代价非常高，至少在进行 HashSet 查找之前进行数字根测试可能是值得的，也许两者都值得。

你可以在这个想法上使用更少的内存，因为 Bloom Filter instead of an exact set (). This would give another candidate-rejection frontend to the full calculation. The guavac BloomFilter implementation 需要一个 "funnel" 函数来将对象转换为字节，在这种情况下应该是 f(x)=x) .

我怀疑 Bloom 过滤不会比精确的 HashSet 检查大获全胜，因为它需要多次内存访问。当您真的负担不起 space 的完整 table，并且您过滤掉的是非常昂贵的东西，例如磁盘访问时，这是合适的。

整数立方根函数（如下）可能比单个缓存未命中更快。如果 cbrt 检查导致缓存未命中，那么当其数据被逐出时，您的代码的其余部分可能也会遭受更多的缓存未命中。

Math.SE 有一个 question about this for perfect squares，但那是关于正方形，而不是立方体，所以出现了 none。不过，那里的答案确实讨论并避免了您方法中的问题。 >.<

你的方法有几个问题：

The problem with using pow(x, 1./3) is that 1/3 does not have an exact representation in floating point, so you're not "really" getting the cube root.所以用cbrt。它不太可能变慢，除非它具有更高的准确性，但需要时间成本。
您假设 Math.pow 或 Math.cbrt 总是 return 一个恰好为整数的值，而不是 41.999999 或其他值。 Java docs 说：

计算结果必须在精确结果的 1 ulp 以内。

这意味着您的代码可能无法在符合规范的 Java 实现上运行。 比较浮点数是否完全相等是一件棘手的事情。 What Every Computer Scientist Should Know About Floating-Point Arithmetic has much to say about floating point, but it's really long. (With good reason. It's easy to shoot yourself in the foot with floating point.) See also Comparing Floating Point Numbers, 2012 Edition，Bruce Dawson 的 FP 系列文章。
我认为它不适用于所有 long 值。 double 只能精确表示最大为 2^53 的整数（64 位 IEEE 双精度中尾数的大小）。 Math.cbrt 个不能精确表示的整数更不可能是一个精确的整数。

FP 立方根，然后测试结果整数，避免了 FP 比较引入的所有问题：

static boolean isCube(long input) {
    double cubeRoot = Math.cbrt(input);
    long intRoot = Math.round(cubeRoot);
    return (intRoot*intRoot*intRoot) == input;
}

（四处搜索后，我在其他 Whosebug / stackexchange 答案上看到其他人也建议使用整数比较方法。）

如果您需要高性能，并且您不介意拥有更多源代码的更复杂的功能，那么有可能。例如，使用具有整数数学的立方根逐次逼近算法。如果您最终达到 n^3 < input <(n+1)^3, theninput` 不是立方体的地步。

this math.SE question.

上有一些方法的讨论

我不会花时间详细研究整数立方根算法，因为 cbrt 部分可能不是主要瓶颈。可能输入解析和字符串-> 长转换是瓶颈的主要部分。

其实我很好奇。原来 Hacker's Delight (use / copying / distributing even without attribution is allowed 中已经有一个整数立方根实现可用。 AFAICT，它本质上是 public 域代码。):

// Hacker's delight integer cube-root (for 32-bit integers, I think)
int icbrt1(unsigned x) {
   int s;
   unsigned y, b;

   y = 0;
   for (s = 30; s >= 0; s = s - 3) {
      y = 2*y;
      b = (3*y*(y + 1) + 1) << s;
      if (x >= b) {
         x = x - b;
         y = y + 1;
      }
   }
   return y;
}

根据 int 中的位数，30 看起来像是一个幻数。将其移植到 long 需要测试。（另请注意，这是 C，但看起来它也应该在 Java 中编译！）

IDK 如果这是 Java 人的常识，但是 32 位 Windows JVM 不使用 server JIT 引擎，也不会优化您的代码.

Answer 5

如果您只是将 int 更改为 long 并将 30 更改为 60，那么黑客喜悦例程似乎对长数字有效。如果您将 30 更改为 61，它似乎不起作用。

我不是很了解这个程序，所以我制作了另一个似乎可以在 Java 中运行的版本。

private static int cubeRoot(long n) {
    final int MAX_POWER = 21;
    int power = MAX_POWER;
    long factor;
    long root = 0;
    long next, square, cube;

    while (power >= 0) {
        factor = 1 << power;
        next = root + factor;
        while (true) {
            if (next > n) {
                break;
            }
            if (n / next < next) {
                break;
            }
            square = next * next;
            if (n / square < next) {
                break;
            }
            cube = square * next;
            if (cube > n) {
                break;
            }
            root = next;
            next += factor;
        }
        --power;
    }
    return (int) root;
}

快速检查长整数是否为立方体的方法（Java）

Fast way to check if long integer is a cube (in Java)

java

algorithm

math

numbers

cubes