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: [mg83501] Re: [mg83410] Fast way of checking for perfect squares?
  • From: DrMajorBob <drmajorbob at bigfoot.com>
  • Date: Wed, 21 Nov 2007 05:56:05 -0500 (EST)
  • References: <16107041.1195623348312.JavaMail.root@m35>
  • Reply-to: drmajorbob at bigfoot.com

I do have a faster method or two, using an "integer square root" function:

Clear[intSqrt, intSqrtGuess, intSqrtIterFirst, intSqrtIter]
intSqrtGuess[x_] := intSqrtIterFirst[x, IntegerPart@Sqrt@N@x]
intSqrtIterFirst[x_, y_] := y + Floor[(x - y^2)/(2 y)]
intSqrt[x_?IntegerQ] := Which[
   x < 4, 1,
   x < 9, 2,
   x < 16, 3,
   x < 25, 4,
   True, FixedPoint[intSqrtIter[x], intSqrtGuess[x]]]
intSqrtIter[x_] = # + Floor[Min[0, x - #^2]/(2 #)] &;

data = Table[RandomInteger[10^10], {5*10^5}];
slowSquareQ = IntegerQ@Sqrt@# &;
squareQ = intSqrt[#]^2 == # &;
fasterSquareQ = intSqrtGuess[#]^2 == # &;
Timing[s1 = Select[data, slowSquareQ];]
Timing[s2 = Select[data, squareQ];]
Timing[s3 = Select[data, fasterSquareQ];]
s1 == s2 == s3

{48.656, Null}

{16.547, Null}

{7.312, Null}

True

Length@s2

2

I know that squareQ works and I believe fasterSquareQ is reliable as  
well... but I don't have a ready proof at the moment.

All this means IntegerPart@Sqrt@N@x is MUCH faster than IntegerQ@Sqrt@x,
which is a bit surprising to me!

Bobby

On Tue, 20 Nov 2007 02:42:09 -0600, <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
>
>
>
>
>
>
>
>
>



-- 

DrMajorBob at bigfoot.com


  • Prev by Date: Re: Fast way of checking for perfect squares?
  • Next by Date: PolarPlot
  • Previous by thread: Re: Fast way of checking for perfect squares?
  • Next by thread: Re: Re: Fast way of checking for perfect squares?