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