From: Joel VanderWerf Date: 2007-02-13T06:33:45+09:00 Subject: Re: What's the correct and fast way to determine if a (gig) number is a perfect square? 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