MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Fast way of checking for perfect squares?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg83537] Re: [mg83509] Re: [mg83410] Fast way of checking for perfect squares?
  • From: DrMajorBob <drmajorbob at bigfoot.com>
  • Date: Thu, 22 Nov 2007 04:53:15 -0500 (EST)
  • References: <200711200842.DAA06940@smc.vnet.net> <1008536.1195647042989.JavaMail.root@m35>
  • Reply-to: drmajorbob at bigfoot.com

And that's the new speed champion for this problem!

It fails for squares of 15-digit and bigger integers, however... and my 
earlier "fasterSquareQ" fails for squares of 32-digit and bigger integers.

Of the three reliable methods, Daniel Lichtblau's is slightly faster than  
my intSqrt method, and the OP's "slowSquareQ" is fastest for perfect  
squares, but slowest for non-squares (which are far more common).

Bobby

On Wed, 21 Nov 2007 05:00:19 -0600, Fred Simons <f.h.simons at tue.nl> wrote:

> Since your integers are not too large, the following works fine and fast:
>
> Select[data, Round[Sqrt[N[#]]]^2 == # &]
>
> Fred Simons
> Eindhoven University of Technology
>
> michael.p.croucher at googlemail.com wrote:
>> Hi
>>
>> Lets say I have a lot of large integers and I want to check to see
>> which ones are perfect squares - eg
>>
>> data = Table[RandomInteger[10000000000], {100000}];
>>
>> I create a function that takes the square root of each one and checks
>> to see if the result is an integer
>>
>> slowSquareQ := IntegerQ[Sqrt[#1]] &
>>
>> This works fine:
>>
>> Select[data, slowSquareQ] // Timing
>>
>> {11.39, {6292614276, 2077627561}}
>>
>> but I am wondering if I can make it faster as my actual application
>> has a LOT more numbers to test than this.  This was a question posed a
>> few years ago in this very newsgroup and the suggestion was to use a
>> test of the form MoebiusMu[#]==0.
>>
>> Well the MoeboisMu function is new to me so I experimented a little
>> and sure enough when you apply the MoebiusMu function to a perfect
>> square number the result is zero.
>>
>> MoebiusMu[4] = 0
>>
>> The problem is that lots of other numbers have this property as well -
>> eg
>>
>> MoebiusMu[8] =0
>>
>> despite this minor problem I determined that applying the test
>> MoebiusMu[#]==0 on a list of integers is fater than my slowSquareQ:
>>
>> mobSquareQ := If[MoebiusMu[#1] == 0, True, False] &
>> Select[data, mobSquareQ]; // Timing
>>
>> gives a result of 8.156 seconds compared to 11.39 for slowSquareQ.  On
>> my test data I had around 39,000 integers that passed this test which
>> is a shame but at least I have eliminated the other 61,000 or so.  So
>> I thought that maybe I can use the faster MoebiusMu test as a filter:
>>
>> SquareQ := If[MoebiusMu[#1] == 0, slowSquareQ[#1], False] &
>> Select[data, SquareQ] // Timing
>> {11.312, {6292614276, 2077627561}}
>>
>> So after all that I have saved just a few tenths of a second.  Not
>> very impressive.  Can anyone out there do any better?
>> Please forgive me if I have made any stupid mistakes but I have a cold
>> at the moment.
>>
>> Best regards,
>> Mike
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>
>
>



-- 

DrMajorBob at bigfoot.com


  • Prev by Date: Re: Fast way of checking for perfect squares?
  • Next by Date: RE: Re: Locator 3D
  • Previous by thread: Re: Fast way of checking for perfect squares?
  • Next by thread: Re: Fast way of checking for perfect squares?