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: [mg83542] Re: Fast way of checking for perfect squares?
  • From: dh <dh at metrohm.ch>
  • Date: Thu, 22 Nov 2007 04:56:31 -0500 (EST)
  • References: <fhu6m6$6pd$1@smc.vnet.net>


Hi Mike,

here is still another pretty fast method:

Calculate all possible squares and take the intersection with your data: 

E.g.:

data=Table[RandomInteger[n=10000000000],{100000}];

t=Range[100000]^2;//Timing

Intersection[t,data]//Timing

this produces:

{0.078,Null}

{0.266,{2876498689}}

this takes a time of approx. 0.3 sec.

hope this helöps, Daniel



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

> 

> 

> 

> 

> 

> 

> 

> 




  • Prev by Date: Re: Get list of function variables?
  • Next by Date: Re: Re: Fast way of checking for perfect squares?
  • Previous by thread: Re: Re: Fast way of checking for perfect squares?
  • Next by thread: Re: Fast way of checking for perfect squares?