Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Fast way of checking for perfect squares?

• To: mathgroup at smc.vnet.net
• Subject: [mg83410] Fast way of checking for perfect squares?
• From: michael.p.croucher at googlemail.com
• Date: Tue, 20 Nov 2007 03:42:09 -0500 (EST)

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

• Follow-Ups:
  • Re: Fast way of checking for perfect squares?
    • From: Fred Simons <f.h.simons@tue.nl>