What's the correct and fast way to determine if a (gig) numb

Ruby
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

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

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:

PARI/GP

– fxn

3

Sam K. wrote:

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)

4

On Feb 11, 2007, at 10:48 PM, Xavier N. 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.

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 = 636511
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.floor2
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.floor2
end
end
x.report(“modular is square (false)”) do
1.upto($r) do
issquare($ns)
end
end
end

5

Hi Joel,

On Feb 11, 11:37 am, Joel VanderWerf [email protected] wrote:

end
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

6

Hi Xavier,

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

On Feb 12, 10:32 am, Xavier N. [email protected] wrote:

attach them below translated to Ruby.

   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

return false unless $squares[11][r % 11]
$s =
Benchmark.benchmark do |x|
end
end
end

Thank you for your support.

Sam

7

Sam K. wrote:

sqrt - sqrt.to_i == 0
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.

8

On Feb 12, 2:07 pm, “Sam K.” [email protected] wrote:

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

9

Sam K. wrote:

def perfect_square? n
sqrt = Math::sqrt(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.

10

On Feb 12, 12:12 pm, Joel VanderWerf [email protected] wrote:

sqrt = n ** 0.5

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

11

On Feb 12, 10:33 pm, Joel VanderWerf [email protected] wrote:

If the number is small, you may do like the following.
x = 123456789123456789
irb(main):003:0> sqrt.floor**2 - x
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
Best is use GMP. Other methods are binary search. Or bigdecimal with
required accuracy