检查长整数是否为多维数据集的快速方法(在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

您可以通过测试模数给定的数字来消除大量候选人.例如,以数字为模的立方体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 3

该黑客的喜悦书有整数立方根这可能是值得移植到64位多头短暂而快速的功能,请参阅下文.

似乎测试一个数字是一个完美的立方体可以比实际计算立方根更快. Burningmath有一种使用" 数字根 "的技术(对数字求和.重复直到它是一个数字).如果数字根是0,1或8,您的数字可能是一个完美的立方体.

这种方法对于置换(数字？)数字的情况非常有价值.如果您可以通过其数字根排除数字,则排除所有排列.

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

无论如何,数字根对计算机来说很快,你甚至可以将你的数字作为一串数字来开始.你仍然需要一个10分频的循环,但你的起点是输入数字的总和,而不是整数,所以它不会有很多分歧.(整数除法比当前CPU的乘法慢一个数量级,但除以编译时常量可以优化乘以+移位与定点逆.希望Java JIT编译器也使用它,也许甚至将它用于运行时常量.)

这加上A.韦伯的测试(input % 819- >搜索45个条目的表格)将排除很多输入,因为不可能是完美的立方体.IDK,如果二进制搜索,线性搜索或散列/集合最好.

这些测试可能是David Eisenstat关于long在数据结构中存储完美立方体的s 集合的想法的前端,该数据结构允许快速存在检查.(例如HashSet).是的,缓存未命中是非常昂贵的,至少在进行HashSet查找之前,数字根测试可能是值得的,可能两者都有.

通过将它用于Bloom Filter而不是精确集(David Ehrman的建议),你可以在这个想法上使用更少的内存.这将为完整计算提供另一个候选拒绝前端.所述guavac BloomFilter实施需要一个"漏斗"的功能来翻译对象字节,在这种情况下,应F(X)= X).

我怀疑Bloom过滤不会是对完全HashSet检查的重大胜利,因为它需要多次内存访问.当你真的无法负担全桌的空间时,这是合适的,你过滤掉的东西就像磁盘访问一样非常昂贵.

整数立方根函数(下面)可能比单个缓存未命中更快.如果cbrt检查导致缓存未命中,那么当其数据被驱逐时,其余代码可能也会遭受更多缓存未命中.

Math.SE 对于完美的正方形有一个问题,但那是关于正方形,而不是立方体,所以这些都没有出现.然而,那里的答案确实讨论并避免了方法中的问题.> <

您的方法有几个问题:

• 使用的问题pow(x, 1./3)是1/3没有浮点的精确表示,所以你不是"真正"获得立方根. 所以使用cbrt.它不太可能变慢,除非它具有更高的准确性和时间成本.

• 您假设Math.pow或Math.cbrt总是返回一个完全是整数的值,而不是41.999999或其他值. Java文档说:

  计算结果必须在精确结果的1 ulp范围内.

  这意味着您的代码可能无法在符合Java的实现上运行. 比较浮点数完全相同是棘手的业务. 每个计算机科学家应该知道什么关于浮点运算有很多关于浮点的说法,但它确实很长.(有充分的理由.很容易用浮点射击自己的脚.)参见比较浮点数,2012年版,布鲁斯道森的系列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;
}

(在搜索之后,我看到其他人在其他stackoverflow/stackexchange答案上也提出了整数比较方法.)

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

关于这个math.SE问题的方法有一些讨论.

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

实际上,我很好奇.事实证明,Hacker's Delight中已经存在整数立方根实现(即使没有归属也允许使用/复制/分发.AFAICT,它本质上是公共域代码.):

// 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;
}

这30看起来像一个基于一个位数的幻数int.将其移植到long需要测试.(另请注意,这是C,但看起来它也应该用Java编译!)

IDK,如果这是Java人员的常识,但32位Windows JVM不使用serverJIT引擎,也不优化您的代码.