MathGroup Archive 2007

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

Search the Archive

Re: Fast way of checking for perfect squares?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg83472] Re: Fast way of checking for perfect squares?
  • From: Jean-Marc Gulliet <jeanmarc.gulliet at gmail.com>
  • Date: Wed, 21 Nov 2007 02:52:27 -0500 (EST)
  • Organization: The Open University, Milton Keynes, UK
  • References: <fhu6m6$6pd$1@smc.vnet.net>

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,
-- 
Jean-Marc


  • Prev by Date: Re: SeriesCoefficient: needs work!
  • Next by Date: Re: Fast way of checking for perfect squares?
  • Previous by thread: Re: Fast way of checking for perfect squares?
  • Next by thread: Re: Fast way of checking for perfect squares?