From: Ondrej Bilka Date: 2007-02-13T22:00:05+09:00 Subject: Re: What's the correct and fast way to determine if a (gig) number is a perfect square? On Feb 12, 10:33 pm, Joel VanderWerf wrote: > Sam Kong wrote: > > > On Feb 12, 12:12 pm, Joel VanderWerf wrote: > >> Sam Kong wrote: > >>> Hi Joel, > >>> On Feb 11, 11:37 am, Joel VanderWerf 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 Best is use GMP. Other methods are binary search. Or bigdecimal with required accuracy