Re: Fast way of checking for perfect squares?
- To: mathgroup at smc.vnet.net
- Subject: [mg83463] Re: Fast way of checking for perfect squares?
- From: Szabolcs Horvát <szhorvat at gmail.com>
- Date: Wed, 21 Nov 2007 02:47:41 -0500 (EST)
- References: <fhu6m6$6pd$1@smc.vnet.net>
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.
You could try working with floating point numbers:
In[1]:= data=Table[RandomInteger[100000000],{100000}];
In[2]:= slowSquareQ:=IntegerQ[Sqrt[#1]]&
In[3]:= Select[data,slowSquareQ]//Timing
Out[3]=
{3.921,{2241009,279841,32307856,1817104,86081284,1002001,72012196,53743561,72880369,94984516,19360000,31956409,8105409,56175025,55875625}}
In[4]:= Select[Sqrt@N[data],FractionalPart[#]==0&]//Timing
Out[4]=
{0.218,{1497.,529.,5684.,1348.,9278.,1001.,8486.,7331.,8537.,9746.,4400.,5653.,2847.,7495.,7475.}}
In[5]:= Round[Last[%]^2]
Out[5]=
{2241009,279841,32307856,1817104,86081284,1002001,72012196,53743561,72880369,94984516,19360000,31956409,8105409,56175025,55875625}
In[6]:= %5 == Last[%3]
Out[6]= True
--
Szabolcs