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
>
>
>
>
>
>
>
>