Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Fast way of checking for perfect squares?

• To: mathgroup at smc.vnet.net
• Subject: [mg83578] Re: Fast way of checking for perfect squares?
• From: m.r at inbox.ru
• Date: Fri, 23 Nov 2007 05:36:01 -0500 (EST)
• References: <200711200842.DAA06940@smc.vnet.net> <1008536.1195647042989.JavaMail.root@m35>

This can be sped up slightly by using listability:

In[1]:= data = RandomInteger[{10^50, 10^60}, 10^5];
 data = Join[data^2, data^2 + 1];

In[3]:= Timing[Pick[data,
 Unitize@ FractionalPart@ Sqrt@
  N[data, 1 + Ceiling@ Log[10, Max@ data]],
 0] == Take[data, 10^5]]

Out[3]= {1.453, True}

Maxim Rytin
m.r at inbox.ru

On Nov 22, 4:03 am, DrMajorBob <drmajor... at bigfoot.com> wrote:
> And that's the new speed champion for this problem!
>
> It fails for squares of 15-digit and bigger integers, however... and my
> earlier "fasterSquareQ" fails for squares of 32-digit and bigger integers.
>
> Of the three reliable methods, Daniel Lichtblau's is slightly faster than  
> my intSqrt method, and the OP's "slowSquareQ" is fastest for perfect  
> squares, but slowest for non-squares (which are far more common).
>
> Bobby
>
>
>
> On Wed, 21 Nov 2007 05:00:19 -0600, Fred Simons <f.h.sim... at tue.nl> wrote:
> > Since your integers are not too large, the following works fine and fast:
>
> > Select[data, Round[Sqrt[N[#]]]^2 == # &]
>
> > Fred Simons
> > Eindhoven University of Technology
>
> > michael.p.crouc... 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
>
> --
>
> DrMajor... at bigfoot.com

• Follow-Ups:
  • Re: Re: Fast way of checking for perfect squares?
    • From: Andrzej Kozlowski <akoz@mimuw.edu.pl>

• References:
  • Fast way of checking for perfect squares?
    • From: michael.p.croucher@googlemail.com