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
- References:
- Fast way of checking for perfect squares?
- From: michael.p.croucher@googlemail.com
- Fast way of checking for perfect squares?