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

*To*: mathgroup at smc.vnet.net*Subject*: [mg83593] Re: [mg83578] Re: Fast way of checking for perfect squares?*From*: DrMajorBob <drmajorbob at bigfoot.com>*Date*: Sat, 24 Nov 2007 04:08:42 -0500 (EST)*References*: <200711200842.DAA06940@smc.vnet.net> <1008536.1195647042989.JavaMail.root@m35> <19518911.1195819385796.JavaMail.root@m35>*Reply-to*: drmajorbob at bigfoot.com

Very nice! originalQ = IntegerQ@Sqrt@# &; treatQ = intSqrt[#]^2 == # &; simon = Round[Sqrt[N[#]]]^2 == # &; lichtblau[ee_] := Module[{prec = Log[10., ee], sqrt}, sqrt = Sqrt[N[ee, prec + $MachinePrecision]]; sqrt == Round[sqrt]] maximRytin[x_] := Pick[x, Unitize@FractionalPart@Sqrt@N[x, 1 + Ceiling@Log[10, Max@x]], 0] k = 60; data = Flatten@ Table[{#^2, #^2 + 1, #^2 - 1} &@ RandomInteger[{10^k, 10^(k + 1)}], {10^4}]; Timing[s1 = Select[data, originalQ];] Timing[s2 = Select[data, treatQ];] Timing[s4 = Select[data, lichtblau];] Timing[s6 = maximRytin@data;] s1 == s2 == s4 == s6 Length /@ {s1, s2, s4, s6} {52.516, Null} {2.015, Null} {1.141, Null} {0.234, Null} True {10000, 10000, 10000, 10000} Bobby On Fri, 23 Nov 2007 04:36:01 -0600, <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 che= cks >> >> 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 applicatio= n >> >> has a LOT more numbers to test than this. This was a question pos= ed = >> 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 littl= e >> >> 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 we= ll = >> - >> >> 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 slowSqu= areQ: >> >> >> 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 wh= ich >> >> 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 filt= er: >> >> >> 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 > > > -- = DrMajorBob at bigfoot.com

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