标签: perfect-square

我正在寻找最快的方法来确定一个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; …

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

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

bool IsPerfectSquare(long input)
{
   // TODO
}

我正在使用C#,但这与语言无关.

奖励点是为了清晰和简洁(这不是代码高尔夫).

编辑:这比我想象的要复杂得多!事实证明,双精度问题有两种表现形式.首先,Math.Sqrt采用了一个不能精确控制的长度(感谢Jon).

其次,当你拥有一个巨大的,接近完美的正方形时,双精度将失去小值(.000 ... 00001).例如,我的实现未通过Math.Pow(10,18)+1的测试(我的报告为真).

我怎么能检查一个数字是否是一个完美的正方形？

速度无关紧要,现在,只是工作.

我想将每个值都放在data一边,我正在考虑使用这样的for循环:

data = rnorm(100, mean=0, sd=1)
Newdata = {L = NULL;  for (i in data)  {i = i*i}  L = i  return (L)}

这是一个代码,用于检查数字是否是完美的正方形.它为什么有效？

static bool IsSquare(int n)
{
    int i = 1;
    for (; ; )
    {
        if (n < 0)
            return false;
        if (n == 0)
            return true;
        n -= i;
        i += 2;
    }
}

我创建了一个函数,用于测试给定参数是否为方数.

在这里阅读方形数字:https://en.wikipedia.org/？title = Square_number

如果数字是平方数,则返回true,否则返回false.负数也会返回错误.

例子:

isSquare(-12) // => false
isSquare( 5) // => false
isSquare( 9) // => true
isSquare(25) // => true
isSquare(27) // => false

现在,我正在使用这种方法:http://jsfiddle.net/marcusdei/ujtc82dq/5/

但是,是否有更短的更简洁的方式来完成工作？

我刚刚开始学习Python并且已经开始做一些问题只是为了帮助提高我的技能,但是我非常坚持这个问题.

制作一个包含所有高达1000的正整数的列表,其正方形可以表示为两个正方形的和(i,例如,整数p,其中p ^ 2 = m ^ 2 + n ^ 2,其中m和n是整数大于0.)

提示:有几种方法.您可能会发现列出所有方形数字会很有帮助.in运算符可能很有用.

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

    numbers=xrange(1001)
    numbers_squared=[x**2 for x in numbers]
    a=[]

    for x in numbers_squared:
        for b in numbers_squared:
            if (x+b)**.5 <= 1001:
                a.append(x+b)
    print a

我得到的问题是Python需要数年才能完成这些计算(我等了大约十分钟,它仍在打印数字).任何关于如何解决这个问题的提示都将非常感激.

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

谢谢!

我的部分代码如下:

class Array
  def square!
    self.map {|num| num ** 2}
    self
  end
end

我打电话的时候:

[1,2,3].square!

我希望得到[1,4,9],但我得到[1,2,3].为什么会这样？我打电话的时候:

[1,2,3].map {|num| num ** 2}

在课堂方法之外,我得到了正确的答案.

我怎么能写一个if-then语句检查输入的整数是否是一个完美的正方形(即如果我取平方根,它也是一个整数:4,9,16,25,36等. )在DrJava？谢谢!

早上好,我是新来的,我带来一个小问题.我无法为以下问题开发有效的算法:我需要找到三个正数x,y和z的组合,以便x + y,x - y,y + z,y - z,x + z和x - z是完美的正方形.问题是开发一种算法,该算法可以找到1到2,000,000之间的x,y和z的所有组合.

目前我使用的是for一个for肯定不会在我有孙子孙女之前结束的.