What's the correct and fast way to determine if a (gig) number is a perfect square?

ruby-talk
1

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.

Thanks in advance.

Sam

2

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.

Easy: compare integers rather than floats.

x = 123456789123456789

sqrt = Math::sqrt(x)
p(x == sqrt.floor**2)

···

--
       vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407

3

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

···

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.

4

I've been able to consult the book today. There is a specialised algorithm to compute integer roots using integer arithmetic, and the integer square test itself. Thus, they guarantee a correct result. I attach them below translated to Ruby.

Some operations would be written using bitwise stuff, but anyway the code performs very poorly (compared to Math::sqrt) according to the benchmarks. If performance is important a solution in C would be worth exploring.

-- fxn

# From Henri Cohen's "A Course in Computational Algebraic Number
# Theory".

# Algorithm 1.7.1 (Integer Square Root) Given a positive integer n,
# this algorithm computes the integer part of the square root of n,
# i.e. the number m such that m^2 <= n < (m + 1)^2.
def isqrt(n)
   x = n
   loop do
     y = ((x + n/x)/2)
     if y < x
       x = y
     else
       return x
     end
   end
end

# Cache the squares modulus 11, 63, 64, and 65. This is used to check
# for non-squares, since a square is a square mod k for all k. The
# choice of these numbers is based on the probability that a non-square
# is a square mod any of them, which is 6/715, less than a 1%.
$squares = {}
[11, 63, 64, 65].each do |m|
   $squares[m] = [false] * m
   (0...(m/2)).each {|i| $squares[m][i**2 % m] = true}
end

# Algorithm 1.7.3 (Square Test). Given a positive integer n,
# this algorithm determines whether n is a square or not,
# and if it is, outputs the square root of n. We assume the
# precomputations made above.
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

require 'benchmark'

$r = 1000

# square of 32248581868698698768678697647823648238462348
$s = 1039971032542162458310099730536273032734192424135131506376453105392112440875299413673104

# non-square, the previous number minus 1
$ns = 1039971032542162458310099730536273032734192424135131506376453105392112440875299413673103

# Just for the sake of curiosity, since the code based on Math::sqrt is not correct.
Benchmark.benchmark do |x|
   x.report("builtin is square (true)") do
     1.upto($r) do
       sqrt = Math::sqrt($s)
       $s == sqrt.floor**2
     end
   end
   x.report("modular is square (true)") do
     1.upto($r) do
       issquare($s)
     end
   end
   x.report("builtin is square (false)") do
     1.upto($r) do
       sqrt = Math::sqrt($ns)
       $ns == sqrt.floor**2
     end
   end
   x.report("modular is square (false)") do
     1.upto($r) do
       issquare($ns)
     end
   end
end

···

On Feb 11, 2007, at 10:48 PM, Xavier Noria wrote:

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.

5

Hi Joel,

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.

Easy: compare integers rather than floats.

x = 123456789123456789

sqrt = Math::sqrt(x)
p(x == sqrt.floor**2)

Yes. Your approach is better than mine.
But it gives a wrong answer for big numbers like 55833579873437812.

--
       vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407

Thanks anyway.

Sam

···

On Feb 11, 11:37 am, Joel VanderWerf <v...@path.berkeley.edu> wrote:

6

Hi Xavier,

I really appreciate your kind help.
I put my comment inline.

> 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.

I've been able to consult the book today. There is a specialised
algorithm to compute integer roots using integer arithmetic, and the
integer square test itself. Thus, they guarantee a correct result. I
attach them below translated to Ruby.

Some operations would be written using bitwise stuff, but anyway the
code performs very poorly (compared to Math::sqrt) according to the
benchmarks. If performance is important a solution in C would be
worth exploring.

-- fxn

# From Henri Cohen's "A Course in Computational Algebraic Number
# Theory".

# Algorithm 1.7.1 (Integer Square Root) Given a positive integer n,
# this algorithm computes the integer part of the square root of n,
# i.e. the number m such that m^2 <= n < (m + 1)^2.
def isqrt(n)
   x = n
   loop do
     y = ((x + n/x)/2)
     if y < x
       x = y
     else
       return x
     end
   end
end

Actually you posted this message, I implemented an algorithm myself.
It's just the way we calculate sqrt with pen and paper.
It might be slow but correct even for big numbers.

def max_digit n, m
  result = 0
  (0..9).each do |i|
    break if ((n * 10) + i) * i > m
    result = i
  end
  result
end

def perfect_square? n
  arr =
  a = n
  while true
    a, b = a / 100, a % 100
    arr.unshift b
    break if a == 0
  end
  remain = 0
  carried = 0
  arr.each do |i|
    num = remain * 100 + i
    digit = max_digit(carried, num)
    remain = num - (carried * 10 + digit) * digit
    carried = (carried * 10 + digit) + digit
  end
  remain == 0
end

I felt ashamed to see the code you posted.OTL

# Cache the squares modulus 11, 63, 64, and 65. This is used to check
# for non-squares, since a square is a square mod k for all k. The
# choice of these numbers is based on the probability that a non-square
# is a square mod any of them, which is 6/715, less than a 1%.
$squares = {}
[11, 63, 64, 65].each do |m|
   $squares[m] = [false] * m
   (0...(m/2)).each {|i| $squares[m][i**2 % m] = true}
end

# Algorithm 1.7.3 (Square Test). Given a positive integer n,
# this algorithm determines whether n is a square or not,
# and if it is, outputs the square root of n. We assume the
# precomputations made above.
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

require 'benchmark'

$r = 1000

# square of 32248581868698698768678697647823648238462348
$s =
103997103254216245831009973053627303273419242413513150637645310539211244
0875299413673104

# non-square, the previous number minus 1
$ns =
103997103254216245831009973053627303273419242413513150637645310539211244
0875299413673103

# Just for the sake of curiosity, since the code based on Math::sqrt
is not correct.
Benchmark.benchmark do |x|
   x.report("builtin is square (true)") do
     1.upto($r) do
       sqrt = Math::sqrt($s)
       $s == sqrt.floor**2
     end
   end
   x.report("modular is square (true)") do
     1.upto($r) do
       issquare($s)
     end
   end
   x.report("builtin is square (false)") do
     1.upto($r) do
       sqrt = Math::sqrt($ns)
       $ns == sqrt.floor**2
     end
   end
   x.report("modular is square (false)") do
     1.upto($r) do
       issquare($ns)
     end
   end
end

Thank you for your support.

Sam

···

On Feb 12, 10:32 am, Xavier Noria <f...@hashref.com> wrote:

On Feb 11, 2007, at 10:48 PM, Xavier Noria wrote:

7

Sam Kong wrote:

Hi Joel,

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.

Easy: compare integers rather than floats.

x = 123456789123456789

sqrt = Math::sqrt(x)
p(x == sqrt.floor**2)

Yes. Your approach is better than mine.
But it gives a wrong answer for big numbers like 55833579873437812.

Wrong how?

irb(main):001:0> x = 55833579873437812
=> 55833579873437812
irb(main):002:0> sqrt = Math::sqrt(x)
=> 236291303.0
irb(main):003:0> sqrt.floor**2 - x
=> -3

Ok, I can see that one problem with my approach is that I should have used #round instead of #floor.

···

On Feb 11, 11:37 am, Joel VanderWerf <v...@path.berkeley.edu> wrote:

--
       vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407

8

Sam Kong wrote:
> Hi Joel,

>> 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.
>> Easy: compare integers rather than floats.

>> x = 123456789123456789

>> sqrt = Math::sqrt(x)
>> p(x == sqrt.floor**2)

> Yes. Your approach is better than mine.
> But it gives a wrong answer for big numbers like 55833579873437812.

Wrong how?

irb(main):001:0> x = 55833579873437812
=> 55833579873437812
irb(main):002:0> sqrt = Math::sqrt(x)
=> 236291303.0
irb(main):003:0> sqrt.floor**2 - x
=> -3

Ok, I can see that one problem with my approach is that I should have
used #round instead of #floor.

I think even if you use #round, the problem won't go away.
Float type cannot generate correct result due to its limited
precision.

Sam

···

On Feb 12, 12:12 pm, Joel VanderWerf <v...@path.berkeley.edu> wrote:

> On Feb 11, 11:37 am, Joel VanderWerf <v...@path.berkeley.edu> wrote:

--
       vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407

9

For example:
irb(main):004:0>
x=981723462487562983749812734972342334123435635465656432452
=> 981723462487562983749812734972342334123435635465656432452

irb(main):005:0> y=x**2
=>
963780956798569484937549463180492938080866374138542452022484415498543617865176348383792466015930367123924038732304

irb(main):006:0> z=Math.sqrt(y)
=> 9.81723462487563e+056

irb(main):007:0> z==x
=> true

irb(main):010:0> z==(x+1000)
=> true

irb(main):011:0> z==(x+10000)
=> true

···

On Feb 12, 2:07 pm, "Sam Kong" <sam.s.k...@gmail.com> wrote:

On Feb 12, 12:12 pm, Joel VanderWerf <v...@path.berkeley.edu> wrote:
> Wrong how?

> irb(main):001:0> x = 55833579873437812
> => 55833579873437812
> irb(main):002:0> sqrt = Math::sqrt(x)
> => 236291303.0
> irb(main):003:0> sqrt.floor**2 - x
> => -3

I think even if you use #round, the problem won't go away.
Float type cannot generate correct result due to its limited
precision.

10

Sam Kong wrote:

Sam Kong wrote:

Hi Joel,

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.

Easy: compare integers rather than floats.
x = 123456789123456789
sqrt = Math::sqrt(x)
p(x == sqrt.floor**2)

Yes. Your approach is better than mine.
But it gives a wrong answer for big numbers like 55833579873437812.

Wrong how?

irb(main):001:0> x = 55833579873437812
=> 55833579873437812
irb(main):002:0> sqrt = Math::sqrt(x)
=> 236291303.0
irb(main):003:0> sqrt.floor**2 - x
=> -3

Ok, I can see that one problem with my approach is that I should have
used #round instead of #floor.

I think even if you use #round, the problem won't go away.
Float type cannot generate correct result due to its limited
precision.

I agree, but I don't think the problem shows up until you have much larger numbers. Is that the case for your program?

In this case, 55833579873437812 cannot be exactly represented by a float, but it doesn't matter for purposes of this calculation.

···

On Feb 12, 12:12 pm, Joel VanderWerf <v...@path.berkeley.edu> wrote:

On Feb 11, 11:37 am, Joel VanderWerf <v...@path.berkeley.edu> wrote:

--
       vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407

11

Best is use GMP. Other methods are binary search. Or bigdecimal with
required accuracy

···

On Feb 12, 10:33 pm, Joel VanderWerf <v...@path.berkeley.edu> wrote:

Sam Kong wrote:

> On Feb 12, 12:12 pm, Joel VanderWerf <v...@path.berkeley.edu> wrote:
>> Sam Kong wrote:
>>> Hi Joel,
>>> On Feb 11, 11:37 am, Joel VanderWerf <v...@path.berkeley.edu> wrote:
>>>> 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.
>>>> Easy: compare integers rather than floats.
>>>> x = 123456789123456789
>>>> sqrt = Math::sqrt(x)
>>>> p(x == sqrt.floor**2)
>>> Yes. Your approach is better than mine.
>>> But it gives a wrong answer for big numbers like 55833579873437812.
>> Wrong how?

>> irb(main):001:0> x = 55833579873437812
>> => 55833579873437812
>> irb(main):002:0> sqrt = Math::sqrt(x)
>> => 236291303.0
>> irb(main):003:0> sqrt.floor**2 - x
>> => -3

>> Ok, I can see that one problem with my approach is that I should have
>> used #round instead of #floor.

> I think even if you use #round, the problem won't go away.
> Float type cannot generate correct result due to its limited
> precision.

I agree, but I don't think the problem shows up until you have much
larger numbers. Is that the case for your program?

In this case, 55833579873437812 cannot be exactly represented by a
float, but it doesn't matter for purposes of this calculation.

--
       vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407