**10 Mar 2007** (updated 31 Mar 2010 at 15:24 UTC)

»
**Perfect Square Test**

A few days ago there was a question in `ruby-talk`
regarding how to test whether a given integer is a perfect
square. You know, an integer is a *perfect square* if
its square root is an integer. As Python and others, Ruby
provides builtin support for arbitrary-precision integers,
but their floats are C types under the hood:

irb(main):051:0> a = 2**512
=> 134078079299425970...(155 digits)
irb(main):052:0> Math.sqrt(a**2) == a
(irb):52: warning: Bignum out of Float range
=> false

and the OP needed to be able to test any integer.

There are libraries such as Pari that offer
that test, but I couldn't compile its Ruby binding on my Mac
and was nonetheless intrigued by the challenge. I recalled a
course on Number Theory where in addition to the proper math
we saw some algorithms in the lab, following Henri Cohen's
*A
Course in Computational Algebraic Number Theory*. At
the beginning of that book the stuff needed to solve that
problem is explained, so I visited the library of the
faculty. This is the approach libraries follow.

The first piece is a way to compute the integer square
root of an integer. Given a positive integer *n*, we
define the *integer square root* of *n* to be the
integer *m* such that *m*^2 ≤ *n* <
(*m* + 1)^2. The algorithm in the book translated to
Ruby is (my notation):

# Algorithm 1.7.1.
def isqrt(n)
x0 = n
loop do
x1 = (x0 + n/x0)/2
return x0 if x1 >= x0
x0 = x1
end
end

Looks like magic isn't it. That's Newton's
method applied to the function *x*^2 –
*n*, though we use only integer arithmetic. Note that
"/" is integer division in Ruby.

If you think for a moment, you'll realise
squares are
rare. As *n* gets bigger *n*^2 gets even bigger.
Thus, between squares there are lots of numbers. If we could
find a quick test for *non-squares* we would speed up
the test a lot in mean, discarding soon true negatives.

That's the main point of Algorithm 1.7.3. We use
the fact
that if *n* is a square, then it is a square modulo
*m* for all *m*. Of course the reciprocal is not
true, for instance any odd integer is a square mod 2. Now,
that implies that if *n* is **not** a square modulo
*m* for some *m*, then it is not a square for
sure. If you take a few well-chosen *m*s the
probability that a non-square is a square modulo all of them
can be less than 1%, this happens with the ones proposed in
the book:

# Cache the squares modulo 11, 63, 64, and 65.
$squares = {}
[11, 63, 64, 65].each do |m|
$squares[m] = [false] * m
(0...(m/2)).each {|i| $squares[m][i**2 % m] = true}
end

Now we join the pieces together to get the test:

# Algorithm 1.7.3.
def issquare(n)
return false unless $squares[64][n % 64]
r = n % 45045 # 45045 = 63*65*11
return false unless $squares[63][r % 63]
return false unless $squares[65][r % 65]
return false unless $squares[11][r % 11]
q = isqrt(n)
return q**2 == n ? q : false
end