Services & Resources / Wolfram Forums / MathGroup Archive
-----

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


  • Prev by Date: simple Button code hangs dynamic evaluation: why?
  • Next by Date: Re: Using FindRoot
  • Previous by thread: Re: Re: Fast way of checking for perfect squares?
  • Next by thread: Re: Fast way of checking for perfect squares?