On Feb 11, 2007, at 8:30 PM, Sam Kong wrote:

> Hello,
>
> I'm solving a math problem in Ruby.
> I need to determine if a number is a perfect square.
> If the number is small, you may do like the following.
>
> def perfect_square? n
>   sqrt = n ** 0.5
>   sqrt - sqrt.to_i == 0
> end
>
> But Float number has limitation on precision.
> Thus the function won't work correctly for big numbers like
> (123456789123456789).
>
> How would you solve such a case?
> It should be fast as well as correct because I will use it repeatedly.

There are faster algorithms based on the fact that most non-squares  
aren't quadratic residues modulo some integers. I remember some is  
explained in Henri Cohen's "A Course in Computational Algebraic  
Number Theory", but do not have the book at hand.

Perhaps you can take a look at the function that implements this test  
in GNU MP, explained here,

   http://www.swox.com/gmp/manual/Perfect-Square-Algorithm.html

or the one in Pari:

   http://www.ufr-mi.u-bordeaux.fr/~belabas/pari/

-- fxn