问题标签 [perfect-square]

我正在寻找确定一个long值是否是完美平方的最快方法（即它的平方根是另一个整数）：

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

这是我现在正在做的非常简单直接的方法：

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

我尝试了不同的解决方案来解决这个问题：

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

可能重复：
确定整数的平方根是否为整数的最快方法

有什么方法可以查看一个数字是否是一个完美的正方形？

我正在使用 C#，但这与语言无关。

清晰和简单的加分点（这并不意味着代码高尔夫）。

编辑：这比我预期的要复杂得多！事实证明，双精度的问题体现在几个方面。首先，Math.Sqrt 需要一个不能精确保持长的双精度（感谢乔恩）。

其次，当你有一个巨大的、近乎完美的正方形时，双精度会丢失小的值（0.000...00001）。例如，我的实现未通过 Math.Pow(10,18)+1 的此测试（我的报告为真）。

我可以依靠吗

或者

检查一个数字是否是一个完美的正方形？为什么或者为什么不？
int a是要判断的数字。我正在使用 Visual Studio 2005。

编辑：感谢所有这些快速的答案。我看到我不能依赖浮点类型比较。（如果我如上所述写，最后一个a会被强制转换为隐式浮动吗？）如果我这样做

我应该把这个e值取多少？

Edit2：嘿，我们为什么不把比较部分放在一边，决定是否(int)有必要？如我所见，有了它，正方形的差异可能很大。但没有它，对于非正方形来说，差异可能很小。也许两者都不会。:-(

我如何检查一个数字是否是一个完美的正方形？

速度是无关紧要的，现在，只是工作。

我需要一些关于如何编写 Python 程序的建议，它会以列表格式为您提供前 n 个完美正方形的列表。输出应如下所示：

这是我到目前为止所拥有的：

现在对于下一部分，我需要创建前 n 个正方形的列表。关于如何做的任何建议？感谢您的时间和建议。

我需要编写一个函数来返回大于其整数参数的第一个完美平方。完美平方是等于某个整数平方的整数。例如，16 是一个完美的正方形，因为 16 = 4 * 4。但是 15 不是一个完美的正方形，因为没有整数 n 使得 15 = n*n。

这是正确的吗？

我正在尝试使用 for 循环在 Visual Basic 中打印平方数列表。我是新手，觉得这很难。我正在编写的程序应该打印数字平方的列表，例如（1、4、9、16 等）。

这是一个检查数字是否是完美平方的代码。为什么它有效？

我刚刚开始学习 Python 并开始做一些问题只是为了帮助培养我的技能，但是我非常坚持这个问题。

制作一个包含最多 1000 的所有正整数的列表，其平方可以表示为两个平方的和，（即整数 p 其中 p^2=m^2+n^2，其中 m 和 n 是整数大于 0。）

提示：有几种方法。您可能会发现拥有所有平方数的列表很有帮助。in 运算符可能很有用。

这是我到目前为止提出的代码：

我遇到的问题是 Python 需要数年时间来完成这些计算（我已经等了大约十分钟，它仍在打印数字）。任何有关如何解决此问题的提示将不胜感激。

ps 重点是使用列表。此外，提示将比解决方案本身更受欢迎。

谢谢你！

当数字不具有完全平方时，它应该返回 false，否则返回根。但在这段代码中，它一直返回根。例如输入 5，根 2。