相关疑难解决方法(0)

我正在寻找最快的方法来确定一个long值是否是一个完美的正方形(即它的平方根是另一个整数):

1. 我通过使用内置Math.sqrt() 函数以简单的方式完成了它,但我想知道是否有办法通过将自己限制为仅整数域来更快地完成它.
2. 维护查找表是不切实际的(因为大约有2 ^31.5个整数,其平方小于2 ⁶³).

这是我现在正在做的非常简单直接的方式:

public final static boolean isPerfectSquare(long n)
{
  if (n < 0)
    return false;

  long tst = (long)(Math.sqrt(n) + 0.5);
  return tst*tst == n;
}

_{注意:我在许多Project Euler问题中使用此函数.因此,没有其他人必须维护此代码.而这种微优化实际上可以产生影响,因为部分挑战是在不到一分钟的时间内完成每个算法,并且在某些问题中需要将此函数调用数百万次.}

我尝试过不同的问题解决方案:

• 经过详尽的测试后,我发现0.5不需要添加Math.sqrt()的结果,至少在我的机器上没有.
• 的快速逆平方根增快,但它给了不正确的结果对于n> = 410881.然而,所建议BobbyShaftoe,我们可以使用FISR劈对于n <410881.
• 牛顿的方法慢了一点Math.sqrt().这可能是因为Math.sqrt()使用类似牛顿方法的东西,但在硬件中实现,因此它比Java快得多.此外,牛顿的方法仍然需要使用双打.
• 一个修改过的牛顿方法,它使用了一些技巧,只涉及整数数学,需要一些黑客来避免溢出(我希望这个函数适用于所有正64位有符号整数),并且它仍然比它慢Math.sqrt().
• 二进制斩甚至更慢.这是有道理的,因为二进制斩波平均需要16遍才能找到64位数的平方根.
• 根据John的测试,or在C++中使用语句比使用语句更快switch,但在Java和C#中,or和之间似乎没有区别switch.
• 我还尝试制作一个查找表(作为64个布尔值的私有静态数组).然后or我会说,而不是开关或声明if(lookup[(int)(n&0x3F)]) { test } else return false; …

我很好奇是否有人能向我解释无分支二进制搜索实现.我在最近的一个问题中看到了它,但我无法想象它将如何实现.我假设如果项目数量非常大,避免分支可能会有用.

我需要编写程序来查找长度为数千位的数字的整数平方根.我不能使用Newton Raphson,因为我没有数据类型来存储和划分这么大的数字.我在C中使用长数组来存储数字.是否有任何算法可以通过迭代数字找到平方根？

编辑:

我不能像GMP一样使用外部库.

如何有效地找到小于给定 int 的最大平方数（即 4、9、16）n？我有以下尝试：

int square = (int)Math.sqrt(number);
return square*square;

但它显然效率低下，无法获得平方根，以便我们可以对其进行平方。

我目前正在寻找一个非常快的整数平方根近似值，其中 floor(sqrt(x)) <= veryFastIntegerSquareRoot(x) <= x

平方根例程用于计算素数，如果仅sqrt(x)检查小于或等于 的值是否为 的除数，则计算速度会快得多x。

我目前拥有的是来自 Wikipedia 的这个函数，稍微调整了一下以使用 64 位整数。

因为我没有其他函数可以比较（或者更准确地说，该函数对于我的目的来说太精确了，而且它可能需要更多的时间，而不是高于实际结果。）

在本网站的 4.4节中,建议二进制搜索数组而不是使用哈希表.那个怎么样？

假设我有一个整数n,我想找到该数字m的平方小于的最大数字n.

这个问题的最佳解决方案是什么？