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

S

Sam Kong

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
 
J

Joel VanderWerf

Sam said:
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)
 
X

Xavier Noria

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
 
X

Xavier Noria

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

# 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
 
S

Sam Kong

Hi Joel,

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.


Thanks anyway.

Sam
 
S

Sam Kong

Hi Xavier,

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

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
 
J

Joel VanderWerf

Sam said:
Hi Joel,



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

Sam Kong

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
 
P

Phrogz

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

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
 
J

Joel VanderWerf

Sam said:
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.
 
O

Ondrej Bilka

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.
Best is use GMP. Other methods are binary search. Or bigdecimal with
required accuracy
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top