Re: Re: Fast way of checking for perfect squares?
- To: mathgroup at smc.vnet.net
- Subject: [mg83531] Re: [mg83472] Re: Fast way of checking for perfect squares?
- From: DrMajorBob <drmajorbob at bigfoot.com>
- Date: Thu, 22 Nov 2007 04:49:36 -0500 (EST)
- References: <fhu6m6$6pd$1@smc.vnet.net> <32011538.1195659270790.JavaMail.root@m35>
- Reply-to: drmajorbob at bigfoot.com
My "fasterSquareQ" is still faster than Daniel's function... though I
can't imagine why!
Clear[intSqrt, intSqrtGuess, intSqrtIterFirst, intSqrtIter]
intSqrtGuess[x_] := intSqrtIterFirst[x, IntegerPart@Sqrt@N@x]
intSqrtIterFirst[x_, y_] := y + Floor[(x - y^2)/(2 y)]
intSqrt[x_?IntegerQ] := Which[
x < 4, 1,
x < 9, 2,
x < 16, 3,
x < 25, 4,
True, FixedPoint[intSqrtIter[x], intSqrtGuess[x]]]
intSqrtIter[x_] = # + Floor[Min[0, x - #^2]/(2 #)] &;
slowSquareQ = IntegerQ@Sqrt@# &;
squareQ = intSqrt[#]^2 == # &;
fasterSquareQ = intSqrtGuess[#]^2 == # &;
lichtblau[ee_] :=
Module[{prec = Log[10., ee], sqrt},
sqrt = Sqrt[N[ee, prec + $MachinePrecision]];
sqrt == Round[sqrt]]
data = Table[RandomInteger[10^10], {5*10^5}];
Timing[s1 = Select[data, slowSquareQ];]
Timing[s2 = Select[data, squareQ];]
Timing[s3 = Select[data, fasterSquareQ];]
Timing[s4 = Select[data, lichtblau];]
s1 == s2 == s3 == s4
{48.266, Null}
{16.5, Null}
{7.281, Null}
{15.937, Null}
True
Bobby
On Wed, 21 Nov 2007 01:52:27 -0600, Jean-Marc Gulliet
<jeanmarc.gulliet at gmail.com> wrote:
> michael.p.croucher at googlemail.com wrote:
>
>> 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.
>
> Daniel Lichtblau's reply to the thread "Changing Pure Function in
> Module" (Jul 14 2001) contains the code of a fast function that tests
> for perfect squareness (see Daniel Lichtblau's squaretest2 function
> below). You should read Daniel's reply for detailed explanations,
> additional code, and benchmarking, at
>
> http://groups.google.com/group/comp.soft-sys.math.mathematica/msg/5b31817c4a697041
>
>
> On my system, squaretest2 is about twice faster than slowSquareQ.
>
> In[8]:= squaretest2[ee_] :=
> Module[{prec = Log[10., ee], sqrt},
> sqrt = Sqrt[N[ee, prec + $MachinePrecision]];
> sqrt == Round[sqrt]]
>
> data = Table[RandomInteger[10000000000], {100000}];
>
> In[10]:= Select[data, squaretest2] // Timing
>
> Out[10]= {6.203, {}}
>
> In[11]:= mobSquareQ := If[MoebiusMu[#1] == 0, True, False] &
> Select[data, mobSquareQ]; // Timing
>
> Out[12]= {8.578, Null}
>
> In[13]:= slowSquareQ := IntegerQ[Sqrt[#1]] &
> Select[data, slowSquareQ] // Timing
>
> Out[14]= {12.235, {}}
>
> HTH,
--
DrMajorBob at bigfoot.com