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

on 2007-02-11 20:30

on 2007-02-11 20:38

Sam Kong 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)

on 2007-02-11 22:48

On Feb 11, 2007, at 8:30 PM, Sam Kong 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: http://www.ufr-mi.u-bordeaux.fr/~belabas/pari/ -- fxn

on 2007-02-12 19:32

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

on 2007-02-12 20:56

Hi Joel, On Feb 11, 11:37 am, Joel VanderWerf <v...@path.berkeley.edu> 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

on 2007-02-12 21:03

Hi Xavier, I really appreciate your kind help. I put my comment inline. On Feb 12, 10:32 am, Xavier Noria <f...@hashref.com> 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

on 2007-02-12 21:14

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

on 2007-02-12 22:08

On Feb 12, 12:12 pm, Joel VanderWerf <v...@path.berkeley.edu> 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

on 2007-02-12 22:25

On Feb 12, 2:07 pm, "Sam Kong" <sam.s.k...@gmail.com> 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

on 2007-02-12 22:34

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

on 2007-02-13 14:00

On Feb 12, 10:33 pm, Joel VanderWerf <v...@path.berkeley.edu> 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