Re: Re: Fast way of checking for perfect squares?

*To*: mathgroup at smc.vnet.net*Subject*: [mg83598] Re: [mg83578] Re: Fast way of checking for perfect squares?*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Sat, 24 Nov 2007 04:11:26 -0500 (EST)*References*: <200711200842.DAA06940@smc.vnet.net> <1008536.1195647042989.JavaMail.root@m35> <200711231036.FAA25206@smc.vnet.net>

This will also work with Mathematica 5.1 and 5.2 (which do not have Unitize but have Pick) with only a slight change: Pick[data, Thread[ FractionalPart@Sqrt@N[data, 1 + Ceiling@Log[10, Max@data]] == 0.]] Andrzej Kozlowski On 23 Nov 2007, at 19:36, m.r at inbox.ru wrote: > 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 > >

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

**Re: Fast way of checking for perfect squares?***From:*m.r@inbox.ru